大家好，欢迎来到IT知识分享网。
原题 https://www.luogu.org/problemnew/show/P1865
本来get到了一个很好的判断素数的方法
O（玄学常数）https://www.luogu.org/blog/nopartyfoucaodong/solution-p3383 （我的luogu博客 嘻嘻）
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> using namespace std; int n,m; bool su(int a){ if(a==1) return 0; if(a==2||a==3) return 1; if(a%6!=1&&a%6!=5) return 0; int temp=sqrt(a); for(int i=5;i<=temp;i+=6) { if(a%i==0||a%(i+2)==0) return 0; } return 1; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x; scanf("%d",&x); if(su(x)) printf("Yes"),cout<<endl; //是质数 else printf("No"),cout<<endl; x=0;
} return 0; }
然而这个方法在一些时候是有弊病的。比如本题区间质数查询时，有些数需要重复的判断多次。用这个方法就会T掉部分点。
一位@Enderturtle大佬给出了另一种方法。
所以说，对于不同的方法，还要注意看它们的优点，适宜什么情况啊（叹气
#include<cmath> #include<cstdio> #include<algorithm> using namespace std; int n,m; int tot[1000005]; bool book[1000005]; void prime(int f) { tot[1]=0; book[1]=true; for(int i=2;i<=f;i++) { if(book[i]==false) { tot[i]=tot[i-1]+1; for(int j=2*i;j<=f;j=j+i) { book[j]=true; } } else tot[i]=tot[i-1]; } } int main() { scanf("%d%d",&n,&m); prime(m); for(int i=1;i<=n;i++) { int l=0,r=0; scanf("%d%d",&l,&r); if(l<1||l>m||r<1||r>m) { printf("Crossing the line\n"); continue; } else { if(book[l]==false) { printf("%d\n",tot[r]-tot[l]+1); continue; } printf("%d\n",tot[r]-tot[l]); } } return 0; }
所以我们换个角度从判断素数，变成判断合数；
合数显然是可以分解质因数的，既然如此，也就说明，质数的倍数（倍数>1）都是合数，所以就有了线性筛（不懂线性筛的同学可以看洛谷[【模板】线性筛素数](https://www.luogu.org/problemnew/show/3383 “【模板】线性筛素数”)）
本质上就是从2开始把它除本身的倍数全部删去，以此类推（这时你可能要问那到这个数的时候怎么判断它是不是质数，事实上，如果自然数N在N-1的时候没有把它标记掉就肯定是质数（具体证明可百度））
区间和可以用前缀和处理；
f[r]-f[l]，如果l是质数还要加1
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://yundeesoft.com/32313.html
