题目描述

求 $1,2,\dots,N$ 中素数的个数。

输入格式

输入一个正整数 $N$。

输出格式

一个整数，表示素数的个数。

样例

20

8

数据范围

• 对于 $40\%$ 的数据：$1 \le N \le 10^6$
• 对于 $80\%$ 的数据：$1 \le N \le 10^7$
• 对于 $100\%$ 的数据：$1 \le N \le 10^8$