质数（素数）

质数个数：
本题明显先求出每个数i前面有多少个质数num[i]，在输入想要的值n找对应的num[n]速度更快。
而更快速的求num[i]则是关键，以往都是一个数一个数判断，但是效率不高。
反向思考一下，先找出有哪些非素数，然后再对素数操作。
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<int> num(1000001,0);
for(int i=2;i<=1000;++i){
if(num[i]==0){
for(int j=i*i;j<=1000000;j+=i){
num[j]=1; //将1000000内所有非质数j对应的num值置1
}
}
}
for(int i=2;i<=1000000;++i){
if(num[i]==0)num[i]=num[i-1]+1;//若i为质数，则赋值为前一个数的num值加1
else{
num[i]=num[i-1];//若i不是质数，则等于前一个数的num值
}
}
int T;
cin>>T;
for(int i=0;i<T;++i){
int n;
scanf("%d",&n);
printf("%d\n",num[n]);
}
return 0;
}</int></vector></iostream>