题解 | 质数统计

#include <iostream>
using namespace std;

// 质数筛 + 前缀和

const int N = 1e6+10; 

int isPrime[N+20]={};
int Prime[N+20]={},cnt=0;

void ElerPrime() { // 欧拉筛
    for(int & i : isPrime) {
        i = 1; 
    }
    isPrime[0] = isPrime[1] = 0;
    for(int i=2;i<N;i++) {
        if (isPrime[i]) {
            Prime[cnt++] = i;
        }
        for(int j = 0;j<cnt && i*Prime[j] <= N;j++) {
            isPrime[i*Prime[j]] = 0;
            if(i%Prime[j] == 0)break; // 性能优化
        }
    }
}

int main() {
    ElerPrime();
    // 前缀和
    for(int i = 0;i<N;i++) {
        isPrime[i]+=isPrime[i-1];
    }
    // 主体
    int n;cin>>n;
    while(n--) {
        int l,r;
        cin>>l>>r;
        cout<<isPrime[r]-isPrime[l-1]<<endl;
    }
    return 0;
}