## 欧拉筛算法及其原理

### 一、欧拉筛法步骤

* 从 $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)