题解 | #质数数量#

思路：

暴力求超时

考虑维护一个素数个数列表即可

a[i]=a[i-1]+1,i为素数；否则a[i]=a[i-1]

#include <bits/stdc++.h>
#define Mlimit 1000000
using namespace std;

int ar[1000002];
bool isP(int n){
    for(int i = 2;i <= sqrt(n);i++)
        if(!(n%i)) return false;
    return true;
}

void calcu(){
    for(int i = 2;i <= Mlimit;i++){
        if(isP(i)) ar[i] = ar[i-1] + 1;
        else ar[i] = ar[i-1];
    }
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int T,n;
    cin>>T;
    calcu();
    while(T--){
        cin>>n;
        cout<<ar[n]<<'\n';
    }
    return 0;
}