题解 | 质数统计

#include <cstring>
#include <iostream>
#include <vector>
#define N 1000001
using namespace std;

bool p[N];
int a[N];

int main() {
    memset(p, true, sizeof(p));
    p[0]=p[1]=false;
    int t, n, x, l, r;
    for(int i=2;i<=1000;i++){       //埃拉托斯特尼筛素数法
        if(p[i]){
            x=i*i;
            while(x<=N){
                p[x]=false;
                x+=i;           
            }     
        }
    }

    a[2]=1;
    for(int i=3;i<=N;i++){          //使用前缀和，方便区间查询
        if(p[i]) a[i]=a[i-1]+1;
        else a[i]=a[i-1];
    }
    
    cin>>t;
    while(t--){
        cin>>l>>r;
        cout<<a[r]-a[--l]<<endl;
    }
    return 0;
}