#NC54580. 素数分布

素数分布

题目描述

素数分布函数 π(n)\pi(n) 表示小于或等于 nn 的素数的数目。例如 π(10)=4\pi(10)=4(2,3,5,72,3,5,7 是素数)。这个函数涉及到许多高等数论的内容,甚至和黎曼猜想挂钩,目前还有很多数学家正在不断探索其中的奥秘。千里之行始于足下,现在你开始关心一个问题:在正整数域中素数的分布是怎么样的。为了探索这个问题,你需要计算出一些 π(n)\pi(n) 的值。

输入格式

第一行一个正整数 TT(T≤1000T\le1000),表示数据的组数。 接下来一共 TT 行,第 i+1i+1 行(1≤i≤T1\le i\le T)表示第 ii 组数据。每行一个正整数 nn(n≤1000n\le1000)。

输出格式

输出 TT 行,第 ii 行对应输入的第 ii 组数据。每行一个非负整数,表示 π(n)\pi(n) 的值。

样例 1

1
10
4

来源

牛客原题