题解 | #漂亮数#

写过素数的个数都知道想要快速找到l,r中间的符合条件的数,可利用筛法

#include <bits/stdc++.h>

using namespace std;

using ll=long long;
const int N=1e8+10;
int p[N],sum[N],cnt;
bool vis[N],st[N];
int t;

void init(){
    for(int i=2;i<=N;i++){
        if(!st[i]) p[cnt++]=i;
        for(int j=0;p[j]<=N/i;j++){
            st[i*p[j]]=1;
            //如果st[i]为质数,i*p[j]就是满足题意的漂亮数
            if(!st[i]) vis[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
    for(int i=1;i<=N;i++) sum[i]=sum[i-1]+(vis[i]?1:0);\\计算前缀和,如果该位置被标记说明是漂亮数,加一即可
}

int main(){
    cin >> t;
    init();
    while(t--){
        ll l,r;
        cin >> l >> r;
        //利用前缀和快速求解
        cout << sum[r]-sum[l-1] << endl;
    }
    return 0;
}