题解 | 质数统计

素数筛+前缀和

只需要用欧拉筛的板子就好了

//欧拉筛
//查找0到n为止的质数
const ll N = 1e6+3;
vector<ll>isp(N);//is prime
vector<ll>primes(N);//record primes
ll cnt = 0;
void oS(ll n) 
{
    isp.assign(n,1);
    isp[0]=isp[1]=false;
    for (ll i=2; i<=n;i++) 
    {
        if(isp[i])primes[cnt++]=i;
        for(ll j=0;j<cnt&&i*primes[j]<=n;j++)
        {
            isp[i*primes[j]]=false;
            if(i%primes[j]==0)break; 
        }
    }
}
void Refra1n()
{  
    oS(N);
    vector<ll>prep(N);
    for(ll i=1;i<N;i++){
        prep[i]=prep[i-1];
        if(isp[i])prep[i]++;
    }
    ll n;cin>>n;
    while(n--){
        ll l,r;cin>>l>>r;
        cout<<prep[r]-prep[l-1]<<endl;
    }
    
}