链接：https://ac.nowcoder.com/acm/problem/22226
来源：牛客网

题目描述

质数（prime number）又称素数，有无限个，质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
例如小于10的质数有2，3，5，7。

输入描述: 

第一行输入一个整数T，表示询问的个数
接下来T行每行输入一个整数n.
1<=T<=1e8,1<=n<=1000000

输出描述: 

对于每个询问n输出小于等于n的的质数的个数。

--------------------------------------------------------------------------------------------
                                 
一开始的时候想着每给出一个限制的数字，就求一回在限制的数字之内质数的数量，
但是求数量这个操作本身在编写出代码的时候就有O(n^2)的时间复杂度，
再加上外面还有一个循环输入限制数的条件直接把程序的时间复杂度提升到了O(n^3)的程度，
最后虽然理论上可以求出答案，但是实际时间超出了限制导致没有通过。

最后是百思不得其解，于是参考了别人的答案。
别人答案的思路大致是这样的。
使用辅助空间的方式，减少时间复杂度。
首先是申请了足够大的数组，能够容得下最大限制数字作为下标
然后通过一系列的操作将原数组下标为质数的下标对应的数值设置为1
下标的数值不是质数的数组元素的值设置为0
然后对这个设置好初始值的数组进行处理
处理方式为，当前数组位置的值等于该数组位置之前所有位置保存的数值加上当前位置上面的数值的和
最后想要知道限制数字以内的所有质数的数量，直接取出以该限制数字为下标的数组位置上面的值即为所求。