题解 | #漂亮数#

我们首先处理出的所有素数，由于时间限制，空间限制很大，我们使用最优版的埃氏筛（时间复杂度），然后对于每一对素数处理，标记，注意他们两个乘起来如果超过了，就不要计算。具体实现见代码：

// Problem: 漂亮数
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/11214/H
// Memory Limit: 2097152 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
#define reg register int
#define INF (1<<30)
#define pb push_back
#define vc vector
#define fst first
#define scd second
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
int read(){
    int res=0,fs=1; char c=getchar();
    while(!(c>='0' && c<='9')){ if(c=='-')fs=-1; c=getchar(); }
    while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
    return res*fs;
}
void print(int x){
    if(x<0) { putchar('-'); x=-x;}
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,cnt,m,ans,tmp,k;
const int N=1e8+5;
bool a[N];
int qzh[N],pri[10000005];
typedef pair<int,int> P;
//struct PROBLEM_SOLVER{
//       int n,m;
//}solver;

//signed main(){
signed main() {
    // ios::sync_with_stdio(false);
    a[1]=1;
    for(int i=2;i*i<=N-5;i++){
        if(a[i]==0){
            for(int j=i*i;j<=N-5;j+=i) {
                a[j]=1;
            }
        }
    }
    rep(i,1,N-5){
        if(a[i]==0) cnt++,pri[cnt]=i;
        a[i]=0;
    }
    rep(i,1,cnt) rep(j,i,cnt) {
        if(pri[i]*pri[j]<=N){
            a[pri[i]*pri[j]]=1;
        }else break;
    }


    rep(i,1,N-5){
        qzh[i]=qzh[i-1]+(a[i]==1);
    }
    cin>>tmp;
    while(tmp--){
        int l,r; 
        l=read(),r=read();
        if(l==0) cout<<qzh[r]<<'\n';
        else 
        cout<<qzh[r]-qzh[l-1]<<'\n';
    }
    return 0;
}