埃氏筛法与欧拉筛（超级详解）

素数的定义：

首先我们明白：素数的定义是只能整除1和本身（1不是素数）。

我们判断一个数n是不是素数时，可以采用试除法，即从i=2开始，一直让n去%i，直到i到了n-1.

代码如下：

 #include<stdio.h> signed main() { int n; for (int i = 2; i <= n - 1; i++) { if (n % i == 0) { printf("%d 不是素数",n); return 0; } } printf("%d 是素数", n); }

但是我们仔细想一下，i是完全没有必要到n-1的，如果到了n/2都除不尽，那么后面就没有必要继续进行试除了。但是你再想想，其实只需要到sqrt(n)就可以了。太细节了

于是，时间复杂度简化：

 #include<stdio.h> signed main() { int n; for (int i = 2; i*i <= n; i++)//等价于i<=sqrt(n)，在这里写成i*i<=n是乘法比开根号要快。 {//这里之所以是<=n而不是<=n-1，可以参考对于9的素数判断。 if (n % i == 0) { printf("%d 不是素数",n); return 0; } } printf("%d 是素数", n); }

但是问题来了，如果一两个数让你去判断，你这么试除一下还行，那要是一堆大的离谱且多的荒谬的数据让你去判断，就算你sqrt，你需要循环的次数也是一个天文数字。这个时候，我们就可以通过一些算法来实现对于大数据（大且多）素数的判断。

埃筛与欧拉筛的实质：

其实埃筛与欧拉筛的实质都且就是围绕这一句话：素数的倍数不是素数。

比如说让你输出——1e5内所有的素数

那我们就筛就好啦，首先咱需要创建一个存素数的数组和一个bool类型的数组（用来判断该元素是否是素数，或者int 类型的数组，因为我们只需要存0或1.但是如果数据实在太大，我们可以vector<int>。这样子就爆不了哈哈。我们也需要注意是否需要开long long 哦。

埃氏筛法：

 //埃氏筛法 int n=1e5; bool shai[n]; //vector<int >shai; int cun[n]; signed main() { int cnt = 0; //如果你用的是vector,则进行注释部分操作 //shai.push_back(1), shai.push_back(1);//在0,1两个位置先添加。0，1都不是素数所以都添1。 //for (int i = 2; i <= n; i++) //{ // shai.push_back(0); //} for (int i = 2; i <= n; i++) { if (!shai[i])//如果没有被标记 { cun[cnt++] = i; for (int j = 2; j <= n; j++) { if (i * j > n)break;//超过数据大小就退掉。 shai[i * j] = 1;//1标记的都是素数的倍数——所以不是素数。 } } } for (int i = 0; i < cnt; i++) { printf("%d ", cun[i]); } }

我们先看一看欧拉筛

欧拉筛：

 #include<iostream> using namespace std; bool a[] = { 1,1 };//同上问一样i=0,i=1的时候都不是质数 ，所以直接标记，数组大小你看着设定，同上文一样太大考虑vector int b[];//存质数 long long n; int main() { int cnt = 0; cin >> n;//看你要查的范围是多大啦。 for (int i = 2; i <= n; i++) { if (a[i] == 0) b[++cnt] = i; for (int j = 1; j <= cnt; j++) { if (i * b[j] > n)break;// 如果超出给出的范围，那么就退出循环 a[i * b[j]] = 1;//素数的倍数不是素数，进行标记。 if (i % b[j] == 0)break;//超级关键的只标记一次 } } for (int i = 1; i <= cnt; i++) { printf("%d ", b[i]); } }

Emmm,感谢JIAN LAI指正。该文已经更新。

<bitset>

update by 2023.7.20.

很早就想更新博客了，但是一直在为了今年acm而刷题。话不多说。

上文提到在n（素数筛范围过大时）使用vector，可行是可行，但是没有必要。因为vector的操作以及所占内存来看是性价比不高的。一般情况，当所给题目n>1e7时候，就转不动了。我们在欧拉筛之所以要引入另一个数组是用于检测该数是否为素数，从而便于判断，如上文的a数组。我们定义为bool类型。在这里引入另外一个类型，bitset，类似于Bool，每一个位置存储一个0或1，由于bool类型是int类型的typedef，因此需要占用4bit的内存空间但是bitset每一个位置所占内存为1bit，更优。

这是其使用方法：

 #include<iostream> #include<bitset>//需要引入头文件 using namespace std; bitset<>a;//定义方式，这里就相当于定义bool a[]; int b[];//存质数 long long n; int main() { int cnt = 0; cin >> n;//看你要查的范围是多大啦。 for (int i = 2; i <= n; i++) { if (a[i] == 0) b[++cnt] = i; for (int j = 1; j <= cnt; j++) { if (i * b[j] > n)break;// 如果超出给出的范围，那么就退出循环 a[i * b[j]] = 1;//素数的倍数不是素数，进行标记。 if (i % b[j] == 0)break;//超级关键的只标记一次 } } for (int i = 1; i <= cnt; i++) { printf("%d ", b[i]); } }

为什么欧拉筛比埃筛要好：

欧拉筛比埃筛要快很多很多倍（大数据的时候10倍是有的）。记得之前做题用埃筛提交1600ms起步，用欧拉筛96ms。

那么为什么呢？

我们看看埃筛，就从2开始，它是素数，所以内循环会标记4,6,8,10,12······一直到退出循环，然后当外层循环到3的时候，它又会标记6,9,12······，在这里我们就能看出一点问题，有数被重新标记了，而且循环到后面重复标记的数量一定不少。这不就浪费时间了嘛。然后它就进阶了~~~。

我们看看欧拉筛，欧拉筛内部有一个很重要的判断语句：if(i%b[j]==0)break; 就是这一个小步骤取消了多余的重复标记。

打个表给你看一下（感谢：平凡@之路）：

 i= 2//当i取2时 j =1 b[1] = 2 i*b[j] = 4 i =3//当i取3时 j=1 b[1] = 2 i*b[j] =6 j=2 b[2] = 3 i*b[j] = 9 i=4//当i取4时 j=1 b[1] = 2 i*b[j] = 8//上面提到为什么退出循环，因为如果不退出循环，就会标记一次12，所以不行 i=5//当i取5时 j=1 b[1] = 2 i*b[j] = 10 j=2 b[2] = 3 i*b[j ]=15 j=3 b[3] = 5 i*b[j] = 25 i=6//当i取6时 j=1 b[1] = 2 i*b[j] =12//这里已经标记了12了。 i=7//当i取7时 j=1 b[1] = 2 i*b[j] = 14 j=2 b[1] = 3 i*b[j] = 21 j=3 b[1] = 5 i*b[j] = 35 j=4 b[1] = 7 i*b[j] = 49

这个自己琢磨一下也能明白个大概吧。

但是我们回过头再想一下欧拉筛，你会发现当你仅仅只需要判断是否是素数而不需要输出的时候。埃筛直接标记即可，但是欧拉筛的使用由于其特定的循环势必会多出一个数组。这就是空间换时间啦！

在这里提供一个题目：

传送门：Problem – 230B – Codeforces

题目就是给出数判断是否只含有三个因子，是就输出YES，否则输出NO。

我们不难发现，如果存在这种数n，那么势必有int k=sqrt(n),k*k=n。然后我们去判断n是否是素数即可。

 #include <iostream> #include <cmath> using namespace std; int a[],b[]; void isans() { int cnt = 0; for (int i = 1; i <= ; i++) a[i] = 1; a[1] = 0; for (int i = 2; i <= ; i++) { if(a[i]==1)b[++cnt] = i; for (int j = 1; j <= cnt; j++) { if (i * b[j] > )break; a[i * b[j]] = 0; if (!(i % b[j]))break; } } } int main() { std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int n; cin >> n; isans(); while (n--) { long long x; cin >> x; long long num = sqrt(x); if (num * num == x && a[num]) cout << "YES\n"; else cout << "NO\n"; } return 0; } 

欧拉筛的时间与空间：

埃氏筛法的时间与空间：