题解 | 质数统计

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int n;
int l,r;
int prime[N],cnt;
bool isprime[N+5];

int main()
{
    cin>>n;
    memset(isprime,true,sizeof(isprime));
    for(int i=2;i<=N;i++)
    {
        if(isprime[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt && i*prime[j]<=N;j++)
        {
            isprime[i*prime[j]]=false;
            if(i%prime[j]==0) break;
        }
    }
    //cout<<cnt<<endl;
    //for(int i=1;i<=100;i++) cout<<prime[i]<<endl;
    while(n--)
    {
        cin>>l>>r;
        int L1=1,R1=cnt;
        while(L1<=R1)
        {
            int mid=L1+R1>>1;
            if(prime[mid]<=l) L1=mid+1;
            else R1=mid-1;
        }
        int L2=1,R2=cnt;
        while(L2<=R2)
        {
            int mid=L2+R2>>1;
            if(prime[mid]<=r) L2=mid+1;
            else R2=mid-1;
        }
        int ans=L2-R1-1;
        //if(prime[R2]==r)  ans++;
        if(prime[R1]==l)  ans++;
        //cout<<L2<<' '<<R1<<endl;
        cout<<ans<<endl;
    }
    return 0;
}