#include <iostream> using namespace std; const int x = 1000001;//使用const是因为能用在下面数组 int a[x];//存答案 bool is_prime[x];//数组内表示是不是质数，是质数为1（真）不是则为0（假） int main() { for(int i = 0;i < x;i++) is_prime[i] = true;//先把is_prime数组内的值都设为1（真）再使用埃式筛筛出不是质数的数变为0（假） is_prime[0] = is_prime[1] = false;//0,1不是质数 for(int i = 2;i < x;i++)//埃式筛开始 { if(is_prime[i])//是质数为真if语句触发 { for(int j = 2 * i;j < x;j += i) { is_prime[j] = false;//筛出不是质数的数都变为0（假） } } }//埃式筛完结 for(int i = 2;i < x;i++) { if(is_prime[i])//是质数为真if语句触发 a[i] = a[i - 1] + 1;//统计质数个数方便下面输出 else//表示不是质数 a[i] = a[i - 1];//不是质数质数个数不变 } int T,n;//题目所给变量 cin >> T; while(T--)//T--表示个数越来越少直到为0（假）while循环不触发 { cin >> n; cout << a[n] << endl;//输出答案 } return 0; }