一、埃拉托斯特尼筛法
基本思想:素数的倍数一定不是素数
实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。
说明:整数1特殊处理即可。背过就好了。
时间复杂度O(nlogn)
空间复杂度为O(n)
#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)
#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)
#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
文章评论
欧拉筛的定义是什么