2.8 KiB
2.8 KiB
欧拉筛算法及其原理
一、欧拉筛法步骤
- 从
i=2开始，如果i还没有被筛掉，则将i加入至素数列表中 - 遍历当前素数列表$primes[]$，筛去 $i \times primes[j]$
(保证$primes[j]*i$不能越界，因为越界了对结果没意义。即
i*primes[j]<=n) - 当遍历到能整除
i的素数primes[j]时，筛去 $i \times primes[j]$，停止对素数列表的遍历 - 重复 $2, 3, 4$，直到所有不超过
n的整数都被遍历过
素数列表中的元素即为所求的不超过 n 的所有素数
二、线性筛代码
附加了输出详细的筛数字过程
#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 , \large p_1 为最小的素数
由于任意小于 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 枚举到 q_2 时，质数数组是由小到大的，当遍历到 p_1 时,有 $i % p_1 == 0$，此时跳出循环，不会再遍历到后面的 $p_2$。
故 n 不会被 p_2 筛去，只会被其最小的素因子 p_1 筛去。
证毕