问题描述

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

输入格式

输入一行一个正整数$N$

输出格式

输出一行一个整数，表示1到N中有多少个素数

样例

10

4

数据范围

• 对于30%的数据：$N≤100$
• 对于70%的数据；$N≤5000$
• 对于100%的数据：$N≤10000000$

来源

• 信息学奥赛之数学一本通
• stong9070整理