You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
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 筛去。
证毕