埃氏筛法（Eratosthenes筛选法）
算法基本思想：要得到自然数n以内的全部素数，必须把不大于n1/2的所有素数的倍数剔除，剩下的就是素数。
给出要筛数值的范围n，找出n以内的素数。依次筛选没有质数因子

#include <iostream>
#include <cmath>

using namespace std;

int main(){
    bool *p= new bool[1000003]();
    int *q=new int[1000001]();
    int T,n,count=0;
    for(int i=2;i<=1000;i++){
        if(p[i]==true)continue;
        for(int j=2;j*i<=1000003;j++){
            p[i*j]=true;
        }
    }
    for(int i=2;i<1000001;i++){
        if(p[i]!=true)count++;
        q[i]=count;
    }
    cin>>T;
    while(T--){
        cin>>n;
        cout<<q[n]<<endl;
    }
    delete []p,q;
    return 0;
}