Đếm số nguyên tố trong 1..n (Count Primes Up to N)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một số nguyên tố là số nguyên lớn hơn 1 chỉ có hai ước dương là 1 và chính nó. Đếm các số nguyên tố p trong đoạn [1,n], bao gồm n nếu n nguyên tố.

Input

Một số nguyên n.

Output

Số lượng số nguyên tố trong [1,n].

Subtask

• Subtask 1 (20%): 1 ≤ n ≤ 100.

• Subtask 2 (30%): 1 ≤ n ≤ 1000.

• Subtask 3 (50%): 1 ≤ n ≤ 10000.

Ví dụ

Ví dụ 1

Input:

10

Output:

4

Giải thích: Các số nguyên tố là 2,3,5,7.

Ví dụ 2

Input:

1

Output:

0

Giải thích: Số 1 không phải nguyên tố.