Bài toán: Số nguyên tố

Tý là một cậu bé rất thích học môn Toán, cậu thường xuyên tìm hiểu, nghiên cứu và giải các bài toán khó. Trong giờ học Toán hôm nay, Tý tìm hiểu về số nguyên tố. Sau khi tìm hiểu khái niệm về số nguyên tố, Thầy giáo có giao cho Tý một bài tập cũng liên quan về số nguyên tố, cụ thể như sau:

Đề bài: Cho trước một số nguyên dương ~N~, hãy ghi ra kết quả số lượng các số nguyên tố nhỏ hơn hoặc bằng ~N~.

Dữ liệu vào:

• Đọc một số nguyên dương ~N~ ~(0 < N \leq 10^6)~.

Dữ liệu ra:

• Ghi ra một số ~K~ là số lượng số nguyên tố thoả mãn đề bài.

Ví dụ:

Input

10

Output

4

Giải thích:

• Các số nguyên tố ~\leq 10~ là: ~2, 3, 5, 7~. Vậy có ~4~ số.

Giới hạn:

• Subtask 1: Có ~30\%~ số test ứng với ~0 < N \leq 1000~.
• Subtask 2: Có ~70\%~ số test ứng với ~0 < N \leq 10^6~.