问题2566--ldx的素数问题

2566: ldx的素数问题

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交

题目描述

众所周知,ldx是个人机,今天他学到了一个新的素数问题,现在给你一个素数分布函数f(n)表示小于或等于n的素数的数目。
例如,f(10)=4(2,3,5,7是素数),这个函数涉及到许多高等数论的内容,甚至和黎曼猜想挂钩,目前还有很多数学家正在不断探索其中的奥秘。
千里之行始于足下,现在你开始关心一个问题:在正整数域中素数的分布是怎么样的。
由于ldx啥也不会,你需要帮助他计算出一些f(n)的值。

输入

第一行一个整数T(T<=1000),表示有T组数据。
接下来一共T行,每行一个正整数n(n<=1000).

输出

每行输出一个正整数,表示f(n).

样例输入 Copy

1
10

样例输出 Copy

4