数论の初见

题目描述

The empress of natural science is mathematics.

The crown of mathematics is number theory.

And Goldbach's conjecture is the most precious jewel on the crown.

输入

多组输入数据

每组数据仅一行，为正整数 n（2 <= n <= 1000000）

输出

对于每组数据，输出一行，为小于等于n的素数的个数

输入样例

9

输出样例

4

思考题

寻找一个单次查询时间复杂度为O（n）的算法