题解 | 质数统计

#include <iostream>
#include <vector>
using namespace std;
const int M =1e6;
vector<bool>is_prime(M,true);
vector<int>prefix(M,0);
void init(){
    is_prime[0]=is_prime[1]=false;
    for(int i=2;i<M;i++){
        if(is_prime[i]){
            for(int j=i*2;j<M;j+=i){
                is_prime[j]=false;
            }
        }
        prefix[i]=prefix[i-1]+(is_prime[i]?1:0);
    }
}
int count_pr(int L,int R){
    return prefix[R]-prefix[L-1];
}
void solve(){
    int a,b;
    cin>>a>>b;
    int jg=count_pr(a,b);
    cout<<jg<<endl;
}
int main() {
   int T;
   cin>>T;
   init();
  
   while (T--) {
     solve();
   }
}
// 64 位输出请用 printf("%lld")

预处理埃氏删+前缀和查询