题目描述

编一个程序，计算1-n范围内素数的个数。输入包含多组数据，输入以0结束。

输入格式

输入包括多组数据，每组数据仅有一个整数n（1<=n<=10000000）。当输入的数为0时，结束输入。

输出格式

对于每组输入的n，输出一行整数，表示1-n（包括n）之间的素数的个数。

样例输入

1
10
65
100
0

样例输出

0
4
18
25

样例解释

1. 输入为1时，1到1范围内没有素数，因此输出0；
2. 输入为10时，1到10之间的素数依次为2、3、5、7，共4个，因此输出4；
3. 输入为65时，1到65之间的素数共有18个，因此输出18；
4. 输入为100时，1到100之间的素数共有25个，因此输出25；
5. 输入为0时，结束输入，无对应输出。