空间换时间

建立一个布尔值数组，记录下每一个数是否为质数，然后累加计算。

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 1000010;

int main(){
    vector<int> v(maxn, 1), sum(maxn, 0);
    for(int i = 2; i <= maxn; ++i){
        if(v[i]){
            for(int j = i + i; j <= maxn; j += i) v[j] = 0;
        }
    }
    for(int i = 2; i <= maxn; ++i){
        if(v[i]) sum[i] = sum[i - 1] + 1;
        else sum[i] = sum[i - 1];
    } 
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        cout << sum[n] << endl;
    }

    return 0;
}