空间限制512MB（这个真的超大） 【题解】一看询问次数这么多足足有1e5；显然就不能用简单的每次询问都去搜一遍。所以很轻易就能想到是要用一下预处理。再看看题目注意关键词质数再看区间范围1e7，很容易就想到用筛法，毕竟一个一个区判断是不是质数复杂度真的太高了（无法接受）。再看看题目有一点两个质数的积，熟悉筛法的同学一下子就可以想到这就是埃氏筛（如果不了解的同学可以百度一下）；所以我们可以开一个数组zs[]表示质数（鉴于本人英语不好就只能用万能的拼音了），f[]表示需要的数；
#include<bits/stdc++.h> using namespace std; const int maxn=1e7+5; bool f[maxn];//满足条件的数 bool zs[maxn];//质数 int s[maxn];//求和 int idx,l,r; int main(){ memset(zs,1,sizeof(zs)); zs[1]=0; f[1]=0; for(int i=1;i<=maxn;i++){ if(zs[i]){/如果是质数 f[i]=1; for(int j=2;j*i<=maxn;j++){ if(j<=i&&zs[j]){ f[j*i]=1;//如果是两个质数相乘就满足条件 } zs[j*i]=0;//一定不是质数 } } s[i]=s[i-1]+f[i]; } scanf("%d",&idx); for(int i=1;i<=idx;i++){ scanf("%d%d",&l,&r); if(f[l]) printf("%d\n",s[r]-s[l]+1); else printf("%d\n",s[r]-s[l]); } return 0; }限于题目中的数据范围，其实不必每次都去跑到1e7，可是记录总的最大右端点做maxn
#include<bits/stdc++.h> using namespace std; const int maxn=10000005; int maxx; bool f[maxn]; bool zs[maxn]; int s[maxn]; int idx,l[100005],r[100005]; int main(){ memset(zs,1,sizeof(zs)); zs[1]=0; f[1]=0; scanf("%d",&idx); for(int i=1;i<=idx;i++){ scanf("%d%d",&l[i],&r[i]); maxx=max(maxx,r[i]); } for(int i=1;i<=maxx;i++){ if(zs[i]){ f[i]=1; for(int j=2;j*i<=maxx;j++){ if(j<=i&&zs[j]){ f[j*i]=1; } zs[j*i]=0; } } s[i]=s[i-1]+f[i]; } for(int i=1;i<=idx;i++){ if(f[l[i]]) printf("%d\n",s[r[i]]-s[l[i]]+1); else printf("%d\n",s[r[i]]-s[l[i]]); } return 0; }用后面这个会快接近三秒；（可能是数据太良心了吧）
