#include using namespace std; const int maxn = 1e6 + 5; bool a[maxn]; int b[maxn]; int T,n; int main() { for(int i = 0;i < maxn;i++)
a[i] = 1;//先假定所有数都为质数 a[0] = a[1] = 0;//零和一都不是质数 for(int i = 2;i < maxn;i++) if(a[i] == 1)//如果是质数，开始判断 for(int j = 2*i;j <= maxn;j += i)//只要是**数的倍数，它就是质数 a[j] = 0;//所以变为0，代表它不是质数 for(int i = 2;i < maxn;i++) if(a[i] == 1)//如果它是质数 b[i] = b[i-1] + 1;//让包括它在内的之前的所有质数个数累加 else //如果它不是质数 b[i] = b[i-1];//不累加，并且继承之前的个数 cin >> T; while(T--) { cin >> n; cout << b[n] << endl;//输出在n之前的所有的质数个数 } return 0; } 原理如下： 根据质数的定义，可以得出：任意数的倍数都不是质数。
一开始假定所有数都为质数，从2计算倍数，只要是2的倍数，都不是质数，所以将以2倍数为下标的bool类型改为0（非0即真0即 假），以此类推3,5,7,9......