Đếm số nguyên tố từ 1 đến N

Cho số nguyên dương N (1 ≤ N ≤ ~10^7~).

Hãy đếm xem có bao nhiêu số nguyên tố trong đoạn từ 1 đến N.

Input:

Một số nguyên N.

Output:

Một số nguyên duy nhất là số lượng số nguyên tố từ 1 đến N.

Ví dụ 1:

Input:

1

Output:

0

Ví dụ 2:

Input:

10

Output:

4