P166PROH - Round 6H - Số gần nguyên tố

https://spoj.com/PTIT/problems/P166PROH

Đề bài: Một số được gọi là số gần nguyên tố nếu nó chỉ có đúng hai ước số nguyên tố. Ví dụ: 26, 62. Hãy đếm số lượng các số gần nguyên tố không vượt quá $N$.

Input: Một số $N$ duy nhất ($1 \leq N \leq 3000$)

Output: Một số nguyên duy nhất là số lượng các số nguyên tố không vượt quá N.

Example:

Input:

11

Output:

2

Solution: Ở đây mình lạm dụng sàng Eratosthenes nên chưa biết duyệt trâu có AC hay không. Cơ bản là mình check số nguyên tố rồi check số nguyên tố đó có phải ước của một số hay không, nếu có thì số lượng ước + 1. Nếu số lượng ước = 2 $\rightarrow$ số đó là số gần nguyên tố.

Code: