题解 | 质数统计

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
using ld = long double;
using PII=pair<ll,ll>;
using PIII=pair<int,pair<int,int>>;
const ld ESP = 1e-10;
const ld PI = acosl(-1);
const int N=1e6+10;
const int M=2e5+10;
// const int mod = 1000000007;
const int mod = 998244353;
//随机化
random_device rd;
mt19937 gen(rd());
uniform_int_distribution<> dis(1, 1000000000);

bool isprime[N + 1];
int phi[N + 1];
int sum[N+1];
std::vector<int> primes;
void init(){
    fill(isprime + 2, isprime + N + 1, true);
    phi[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (auto p : primes) {
            if (i * p > N) {
                break;
            }
            isprime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }
    for(int i=1;i<=N;i++){
        if(phi[i]==i-1)sum[i]=1;
        else sum[i]=0;
        sum[i]+=sum[i-1];
    }
}
void solve(){
    int l,r;
    cin>>l>>r;
    cout<<sum[r]-sum[l-1]<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int _=1;
    cin>>_;
    init();
    while(_--){
        solve();
    }
    return 0;
}