数组-筛法求素数 题目描述 筛法求素数，指的是每次将一个素数的所有的倍数去掉，如果当前的数没有被比它小的数去掉过，那么当前的数就是素数。 比如1 2 3 4 5 6 7 8 9 10 11 12 1

数组-筛法求素数

题目描述

pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
筛法求素数，指的是每次将一个素数的所有的倍数去掉，如果当前的数没有被比它小的数去掉过，那么当前的数就是素数。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
比如1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1不是素数。不用管。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2是素数，那么2的所有的倍数要被去掉。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3是素数，那么3的所有的倍数要被去掉。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
4 被去掉了。不用管。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
。。。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
这样做下去我们就可以筛选出所有的指定范围内的素数了。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
你的任务是求小于等于n的素数的个数count。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
做完这道题后感兴趣的同学可以将n/count 的值打印输出来看看。pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
 

输入

pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行输入一个整数T，表示询问的个数pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
接下来T行每行输入一个整数n.

输出

pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
对于每个询问n输出小于等于n的的素数的个数。

样例输入 

2
10
1000000

样例输出

4
78498

提示

pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 <= T <= 10⁸pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 <= n <= 10⁶pLH100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
要注意n和T的范围哦，算算自己的程序能不能在1秒内算出结果，普通计算机一秒钟大约是10⁷到10⁸的计算量