题目描述

给定一个正整数$\red{N}$，求出$\red{1}$到$\red{N}$中有多少个素数。

输入格式

输人一行一个正整数$\red{N}$。

输出格式

输出一行一个整数，表示$\red{1}$到$\red{N}$中有多少个素数。

样例

输入样例

10

输出样例

4

提示

对于$\red{30\%}$的数据:$\red{N≤}$$\red{100}$

对于$\red{70\%}$的数据:$\red{N≤}$$\red{5000}$

对于$\red{100\%}$的数据:$\red{N≤}$$\red{10000 000}$