#1459. 筛选法求质数 暂未评定

时间限制:1000 ms 内存限制:128 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

筛法求素数,指的是每次将一个素数的所有的倍数去掉,如果当前的数没有被比它小的数去掉过,那么当前的数就是素数。

比如1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

1不是素数。不用管。

2是素数,那么2的所有的倍数要被去掉。

3是素数,那么3的所有的倍数要被去掉。

4 被去掉了。不用管。

。。。

这样做下去我们就可以筛选出所有的指定范围内的素数了。

你的任务是求小于等于n的素数的个数count。

做完这道题后感兴趣的同学可以将n/count 的值打印输出来看看。

输入格式

第一行输入一个整数T,表示询问的个数

接下来T行每行输入一个整数n.

输出格式

每行一个对于每个询问n输出小于等于n的的素数的个数。

样例

样例输入:

2
10
1000000

样例输出:

4
78498

数据范围与提示