1468: 素数有多少
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：16
Solved：6
Description
不允许普通用户打印题目，请教师登录后使用。如有疑问请联系管理员!
Input
第一行包含一个整数(1 ≤k≤100000),表示测试用例的个数。输入一个整数n(1<=n<=1,000,000);
Output
每个测试用例输出一行，输出区间[2,n]中素数的个数。
Sample Input Copy
3
10
20
30Sample Output Copy
4
8
10HINT
提示
因为本问题中提问次数最大为10万次，每次问到的最大范围为[2,1000000]次，因此必须注意提高程序的效率，否则将出现“超过时间限制”的错误。
具体注意事项有：
1、为了减少重复计算，利用先计算表格，然后查表的方式解决。即“一次计算，多次查询”。也就是说，可以通过先生成不超过n的素数个数的表，存放在数组a[ ]中，a[k]的值表示不超过k的素数的个数。遇到提问[2,k]，直接根据此表回答结果即可。
2、尽量提高“素性测试”的效率。减少循环次数，或者使用素数筛方法。
3、判断n是否存在因子的循环，如果写成如下形式；
for( i=2;i<sqrt(n); i++)
{
.................
}
这个循环的效率比较低，因为每循环一次都需要重新计算n的平方根，其实这个计算只需要做一次。因此以上循环可以改成如下形式，提高运行效率。
int gen=sqrt(n);
for( i=2; i<=gen; i++ )
{
.......................
}