题目描述

输入一个整数n，请问1~n范围内有多少个素数？

输入格式

一个整数n（n≤10000000）

输出格式

输出1~n范围内素数的个数。

样例输入

20

样例输出

8

样例解释

1到20之间的素数依次为2、3、5、7、11、13、17、19，一共统计出8个素数，所以该样例的输出为8。