题解 | 质数统计

#include <algorithm>
#include <bits/stdc++.h>
#include <vector>
using namespace std ;

const int N=1e6+5;
vector<int> prime(N);
vector<bool> vis(N);
int idx=0;
void Euler(){
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++idx] = i;
        for(int j = 1; prime[j]*i <= N; j++){
            vis[prime[j]*i] = true;
            if(i % prime[j] == 0) break;
        }
    }

}

int  main(){
    Euler();
    int n;cin>>n;
    for(int i = 1; i <= n; i++){
        int l,r;cin>>l>>r;
        int Lpos = lower_bound(prime.begin(), prime.begin()+idx, l) - prime.begin();
        int Rpos = upper_bound(prime.begin(), prime.begin()+idx, r) - prime.begin();
        cout<< Rpos - Lpos  <<endl;
    }
    return 0;
}