判断质数的方法有很多，首先是最简单的试除法，判断n以内的质数的话时间复杂度为n*sqrt(n)当然是很慢的了
下面提供三种判断质数的方法：
首先是跑5051ms的这个是埃拉托斯特尼筛法 且不加优化 核心质数的倍数一定不是质数
#include<iostream> #include<cmath> #include<cstdio> #include<iomanip> #include<algorithm> #include<ctime> #include<queue> #include<stack> #include<string> #include<cstring> #include<map> #include<vector> using namespace std; inline long long read() { long long x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const long long maxn=10000002; long long n,m; long long a[maxn]; void bwy()//闻道玉门犹被遮，应将性命逐轻车 { for(long long i=1;i<=m;i++)a[i]=1; a[1]=0; for(long long i=1;i<=m;i++) { if(a[i]==1) { for(long long j=i<<1;j<=m;j+=i) { a[j]=0; } } } } int main() { //freopen("1.in","r",stdin); m=read();n=read(); bwy(); for(long long i=1;i<=n;i++) { long long x; x=read(); if(a[x]==1)printf("Yes "); else printf("No "); } return 0; }
从当前质数的1倍筛到n/i倍即可。
然后第二种是其优化算法 也是竞赛之中使用最多的筛法。经观察发现可以从i*i筛到n/i;这样即可。
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> #include<ctime> #include<vector> #include<queue> #include<map> #include<stack> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int a[10000002]; void wy() { a[1]=1; for(int i=2;i<=n;i++) { if(a[i]==0) { for(int j=i;j<=n/i;j++) { a[i*j]=1; } } } } int main() { //freopen("1.in","r",stdin); n=read();m=read(); wy(); for(int i=1;i<=m;i++) { int x; x=read(); if(a[x]==0)printf("Yes "); else printf("No "); } return 0; }
第三种则是真正的线性筛法了，埃拉筛法。找到每个数的最小质因子使筛出的数字只被唯一筛出~
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iomanip> #include<ctime> #include<vector> #include<queue> #include<map> #include<stack> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m; int prime[10000002],v[10000002],top=0;//v数组里存在i的最小质因子 void wy() { memset(v,0,sizeof(v)); for(int i=2;i<=n;i++) { if(v[i]==0){v[i]=i;prime[++top]=i;} for(int j=1;j<=top;j++) { if(prime[j]>v[i]||prime[j]>n/i)break; v[i*prime[j]]=prime[j]; } } } int main() { //freopen("1.in","r",stdin); n=read();m=read(); wy(); for(int i=1;i<=m;i++) { int x; x=read(); if(v[x]==x)printf("Yes "); else printf("No "); } return 0; }
You're perfectly wrong for me.