题解 | #漂亮数#

我觉得这题不就是求质数加前缀和嘛（好像其他大佬也是呢）

先欧拉筛一遍，欧拉筛时再记录一下漂亮数，做一下前缀和,最后再提取就行了！

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

int p[100000000],b[100000005],cnt,flag[100000005];

void init(){
    for(int i = 2;i <= 1e8;i++){
        if(!b[i]){
            p[++cnt] = i;
        }
        for(int j = 1;j <= cnt&&i*p[j]<=1e8;j++){
            b[i*p[j]] = 1;
            if(!b[i]) flag[i*p[j]] = 1;
            if(i%p[j]==0)break;
        }
    }
    for(int i = 2;i <= 1e8;i++){
        flag[i]+=flag[i-1];
    }
}

int main(){
    init();
    int T,l,r,ans,x,y;
    cin >> T;
    while(T--){
        cin >> l >> r;
        cout << flag[r]-flag[l-1] << endl;
    }
    return 0;
}