文章目录[隐藏]
一、埃拉托斯特尼筛法
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。背过就好了。
时间复杂度O（nlogn）
空间复杂度为O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int maxn = 10000001; int vis[maxn]; void prime(int ); int main(){ int n,m; scanf("%d%d",&n,&m); prime(n); for(int i = 1;i <= m;++i){ int x; scanf("%d",&x); if(vis[x]) printf("Yes\n"); else printf("No\n"); } return 0; } void prime(int n){ for(int i = 0;i < n;++i) vis[i] = true; vis[0] = vis[1] = 0; for(int i = 2;i * i < n;++i) { if (!vis[i]) continue; for (int j = i; i * j < n; j++) vis[ i*j ] = 0; } } |
二、欧拉筛法（线性筛法）
时间复杂度O（n）
空间复杂度O（n）
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; void is_prime(int); const int maxn(100001); int prime[maxn]; bool vis[maxn]; int tot; int main(){ int n,m; scanf("%d%d",&n,&m); is_prime(n); for(int i=1;i<=m;++i){ int x; scanf("%d",&x); if(vis[x]) printf("Yes\n"); else printf("No\n"); } return 0; } void is_prime(int list) { memset(vis,true,sizeof(vis)); vis[1]=false; for(int i=2;i<=list;++i){ if(vis[i]) prime[++tot]=i; for(int j=1;j<=list&&i*prime[j]<=list;++j){ vis[i*prime[j]]=false; if(i%prime[j]==0) break; } } } |
三、一个奇怪的筛法
时间复杂度 接近O(n)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> using namespace std; const int maxn(10000005); bool he[maxn]; int n,m; int main() { scanf("%d%d",&n,&m); he[0]=he[1]=1; int t; for(int i=4;i<=n;i+=2) he[i]=1; for(int i=2;i<=n;i++) if(!he[i]) for(int j=i*2;j<=n;j+=i) he[j]=1; for(int i=1;i<=m;i++){ scanf("%d",&t); if(he[t]) printf("No\n"); else printf("Yes\n"); } return 0; } |
洛谷：P3383
