题解 | 质数统计

#include<bits/stdc++.h>
using namespace std;
const long long N=1e6+10;
int prime[N];
bool vis[N];
int cnt=0;

void Ol(int n){
    memset(prime,0,sizeof(prime));
    memset(vis,0,sizeof(vis));
    for (int i=2;i<=n;i++) {
        if (!vis[i]) prime[cnt++]=i;
        for (int j=0;j<cnt && prime[j]*i<=n;j++) {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    Ol(N);
    int n,l,r;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>l>>r;
        int ans=0,temp=0;
        while(temp<cnt){
            if(prime[temp]>=l&&prime[temp]<=r){
                ans++;
                temp++;
            }else temp++;
        }
        cout<<ans<<endl;
    }
    
}

欧拉筛加暴力查找