题目描述

编一个程序，计算 $1$ 到 $n$ 范围内素数的个数。

输入格式

包括多组数据。每组数据仅有一个整数 $n$。输入以 $0$ 结束。

输出格式

对于每组数据输入，输出一行，为 $1$ 到 $n$（包括 $n$）之间的素数的个数。

1
10
100
0

0
4
25

样例解释

$1$ 到 $1$ 之间无素数，输出 $0$。 $1$ 到 $10$ 之间素数为 $2, 3, 5, 7$，共 $4$ 个。 $1$ 到 $100$ 之间共有 $25$ 个素数。

数据范围

$1 \le n \le 10000000$，多组数据，以 $0$ 结束输入。