题意：求 [ L , R ] 范围内是质数或两个质数乘积的数的个数

魔改线性筛素数即可，预处理1~N_max的所有符合要求的数的数量，对于每组询问 O(1) 回答。

对于每个素数，肯定是要计算的。在后面排除合数的时候，判断当前数是不是素数，若是，也算入其中。

用前缀和优化，对于一组询问[L,R]，回答 cnt[R]-cnt[L-1] 即可

#include
     
      using namespace std;template
      
        inline void read(T &_a){    bool f=0;int _ch=getchar();_a=0;    while(_ch<'0' || _ch>'9'){
   if(_ch=='-')f=1;_ch=getchar();}    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}    if(f)_a=-_a;}const int maxn=10000000;bool nprime[maxn+1],like[maxn+1];int cnt[maxn+1],Q,tot,pri[maxn+1];inline void __super_boluo_banana_ship(){    for (register int i=2;i<=maxn;++i)    {        if(!nprime[i]) pri[++tot]=i,like[i]=true;        for(register int v=1;v<=tot&&pri[v]*i<=maxn;++v)        {            if(!nprime[i]) like[pri[v]*i]=true;            nprime[pri[v]*i]=true;            if(i%pri[v]==0) break;        }    }    for (register int i=2;i<=maxn;++i) cnt[i]=cnt[i-1]+like[i];}int main(){    freopen("prime.in","r",stdin);    freopen("prime.out","w",stdout);    read(Q);    __super_boluo_banana_ship();  // 超级菠萝香蕉船    for (register int L,R;Q;--Q)    {        read(L); read(R);        printf("%d\n",cnt[R]-cnt[L-1]);    }    return 0;}