Problem1925--n盏灯

1925: n盏灯

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Submit

Description

有n盏灯,序号为1到n。在初始状态下,所有的开关都是关的。
有n个开关控制这n盏灯,第i个开关控制第i盏灯
现在从1开始计数,每遇到一个素数就把该素数对应的倍数序号的开关朝相反的方向拨一下,一直到最后一个小于等于n的素数为止。请统计最后有多少盏灯是开的?

Input

多组输入,每组输入一个n(2<=n<=106)。

Output

每组数据,输出开的灯的盏数

Sample Input Copy

10

Sample Output Copy

7