|
|
|
|
|
## 欧拉筛算法及其原理
|
|
|
|
|
|
|
|
|
|
|
|
### 一、欧拉筛法步骤
|
|
|
|
|
|
|
|
|
|
|
|
* 从 $i=2$ 开始，如果 $i$ 还没有被筛掉，则将 $i$ 加入至素数列表中
|
|
|
|
|
|
* <font color='red' size=4><b>遍历当前素数列表$primes[]$</b></font>，<font color='blue' size=4><b>筛去 $i \times primes[j]$</b></font>
|
|
|
|
|
|
(保证$primes[j]*i$不能越界，因为越界了对结果没意义。即$i*primes[j]<=n$)
|
|
|
|
|
|
* 当遍历到能整除 $i$ 的素数 $primes[j]$ 时，筛去 $i \times primes[j]$，<font color='red' size=4><b>停止对素数列表的遍历</b></font>
|
|
|
|
|
|
* 重复 $2, 3, 4$，直到所有不超过 $n$ 的整数都被遍历过
|
|
|
|
|
|
|
|
|
|
|
|
素数列表中的元素即为所求的不超过 $n$ 的所有素数
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 二、线性筛代码
|
|
|
|
|
|
**附加了输出详细的筛数字过程**
|
|
|
|
|
|
```cpp {.line-numbers}
|
|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
|
|
|
|
|
|
const int N = 1e5 + 10;
|
|
|
|
|
|
int primes[N], cnt;
|
|
|
|
|
|
bool st[N];
|
|
|
|
|
|
void get_primes(int n) {
|
|
|
|
|
|
for (int i = 2; i <= n; i++) {
|
|
|
|
|
|
if (!st[i]) primes[cnt++] = i;
|
|
|
|
|
|
bool flag = (primes[0] * i <= n);
|
|
|
|
|
|
if (flag) printf("i=%d ", i);
|
|
|
|
|
|
for (int j = 0; primes[j] * i <= n; j++) {
|
|
|
|
|
|
st[primes[j] * i] = true;
|
|
|
|
|
|
printf("%d ", primes[j] * i);
|
|
|
|
|
|
if (i % primes[j] == 0) break;
|
|
|
|
|
|
}
|
|
|
|
|
|
if (flag) puts("");
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
get_primes(200);
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
|
|
|
|
|
```
|
|
|
|
|
|
|
|
|
|
|
|
### 三、欧拉筛法原理
|
|
|
|
|
|
|
|
|
|
|
|
#### 1、每个合数都会被筛去
|
|
|
|
|
|
**证明：**
|
|
|
|
|
|
若 $n$ 为合数，设其质因子分解为 $$\LARGE n = p_1 \times p_2\times ...\times p_q$$，其中$\large p_i$可以等于$\large p_j$ , <font color='red' size=4><b>$\large p_1$ 为最小的素数</b></font>
|
|
|
|
|
|
|
|
|
|
|
|
由于任意小于 $p_1$ 的质数都不能整除 $p_2 \times ... \times p_q$，所以 $n$ 会在遇到$primes[j]=p_1$时，也就是 $\large i = p_2 \times ...\times p_q$ 时被筛去。
|
|
|
|
|
|
|
|
|
|
|
|
**证毕**
|
|
|
|
|
|
|
|
|
|
|
|
#### 2、每个合数只会被筛去$1$次
|
|
|
|
|
|
|
|
|
|
|
|
**反证法：**
|
|
|
|
|
|
设合数 $n$ 即被 **质数**$\large p_1$ 筛去，也被 **质数**$\large p_{2}$ 筛去。那么有 $\large n = q_1 \times p_1 = q_2 \times p_2$，其中 $p_1$ 和 $p_2$ 均是 $n$ 的素因子。
|
|
|
|
|
|
|
|
|
|
|
|
不妨设 $\large p_1 < p_2$，则有$q_1>q_2$,且$p_1 和 p_2$ 互素，故有 $\large p_1 | q_2$,也就是$\large q_2 \% p_1=0$
|
|
|
|
|
|
|
|
|
|
|
|
当$i$ <font color='blue' size=4><b>枚举到</b></font> $q_2$ 时，质数数组是由小到大的，当遍历到 $p_1$ 时,有 $i \% p_1 == 0$，此时跳出循环，不会再遍历到后面的 $p_2$。
|
|
|
|
|
|
|
|
|
|
|
|
故 $n$ 不会被 $p_2$ 筛去，只会被其最小的素因子 $p_1$ 筛去。
|
|
|
|
|
|
|
|
|
|
|
|
**证毕**
|
|
|
|
|
|
|
|
|
|
|
|
### 四、网上精彩视频讲解
|
|
|
|
|
|
[点我来看](https://www.bilibili.com/video/BV1Lv41177fA/)
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
### 五、练习题
|
|
|
|
|
|
[洛谷 $P3912$ 素数个数](https://www.luogu.com.cn/problem/P3912)
|
|
|
|
|
|
|
|
|
|
|
|
### 六、其它素数筛法及原理
|
|
|
|
|
|
[点我阅读](https://www.cnblogs.com/kentle/p/14205126.html)
|
