题解 | #质数数量#

#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 10; int a[N],s[N]; int main() { for( int i = 2 ; i < N ; i ++ ) for( int j = 2 ; j <= sqrt(i) ; j ++ ) if( i % j == 0 ) { a[i] = 1; break; }

for(int i=2;i<N;i++)
{
    if(a[i] == 0) s[i] = s[i-1] + 1;
    else s[i] = s[i-1];
}

int t , n;
cin >> t;
while( t -- )
{
    int sum = 0;
    cin >> n;
    cout<<s[n]<<endl;
}
return 0;

}