题解 | 质数统计(我爱前缀和）

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+3;
bool p[N];
int sum[N]={0};
void isprime()
{
    for(int i=0;i<N;i++)
    {
        p[i]=true;
    }    
    p[0]=p[1]=false;
    for(int i=2;i<N;i++)
    {
        
        if(p[i])
        {
            for(long long j=(long long)i*i;j<N;j+=i)
            p[j]=false;
        }
    }
    for(int i=0;i<N;i++)
    {
        sum[i]=sum[i-1]+(p[i]?1:0);//是素数就要再加1
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin>>t;
    isprime();
    while(t--)
    {
        
        int ans=0;
        int l,r;
        cin>>l>>r;
        cout<<sum[r]-sum[l-1]<<'\n';
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

埃氏筛，打表打他娘的，因为数据范围是1e6，直接找要超时，打表不用long long 数据还要爆，我们直接一个雷霆前缀和把他优化了。时间复杂度是O(1)。