1.普通筛
主要思想
其实就是简单的数学
检测 2~ x /2 有没有 x 能整除的数
如果有，说明 x 是合数
如果没有，说明 x 是质数
代码实现
const int N = 1e5;
int cnt,Prime[M];
bool is_P(int x){
for (int i = 2; i < x; i ++){
if (x % i == 0) return false;
}
return true;
}
void Get_Prime(int n){
for (int i = 2; i <= n; i++) {
if (is_P(i)) Prime[++cnt] = i;
}
}
时间复杂度
O(nlogn)
2.埃氏筛
主要思想
如果 x 没有被标记
将 x 加入 数组
将 n 以内的 x 的倍数标记
代码实现
const int N = 1e8 , M = 1e5;
bool isPrime[N];//如果为true，说明是合数；如果是false，说明是质数
int cnt,Prime[M];//存储质数的数组
void Get_Prime(int n){
for (int i = 2; i <= n; i++) {
if (!isPrime[i]) {//是质数
Prime[++cnt] = i;
for (int j = i * 2; j <= n; j += i) {//标记合数
isPrime[j] = true;
}
}
}
}
时间复杂度
O(nloglogn)
3.欧拉筛
注：文章重点，会注重讲这里
这个筛法的原理牵扯到一些数学知识
先讲 \Large \color{Red}核心原理 :
合数仅被以下公式筛掉
\Large “最小质因数 \times 最大因数（非自己）= 合数”
先贴代码再讲原理
const int N = 1e8+10,M = 1e6+10;
bool isPrime[N];
//0表示：i是素数
int Prime[M], cnt = 0;
//Prime存质数
void GetPrime(int n){
for(int i = 2; i <= n; i++) {
if(isPrime[i]) Prime[++cnt] = i; //i成为下一个素数
for(int j = 1; j <= cnt && i*Prime[j] <= n/*不超上限*/; j++) {
//从Prime[1]，即最小质数2开始，逐个枚举已知的质数，并期望Prime[j]是(i*Prime[j])的最小质因数
//当然，i肯定比Prime[j]大，因为Prime[j]是在i之前得出的
isPrime[i*Prime[j]] = 0;
if(i % Prime[j] == 0)//i中也含有Prime[j]这个因子
break; //重要步骤。见原理
}
}
}
原理概述
外层循环遍历 2 ~ n ，和其他质数筛一样
如果 i 仍未被标记，说明是质数，加入数组
内层循环从小到大枚举质数，尝试通过 i \times Prime_j 来筛掉合数，其中，我们期望 Prime_j 是这个合数的最小质因子（这是线性复杂度的条件，以下简称筛条件）
\large \mathbf 那么，是怎么保证筛条件的？
内层循环中，就有一个判断保证了它
if(i % Prime[j] == 0)
break;
以下变量中, t < s < j < b
i \mod Prime_j == 0 时刚好需要停止的理由是:
-
i 的最小质因数必然是 Prime_j
如果 i 的最小质因数是 Prime_s ，由于我们是从小到大枚举的，所以在遍历到 Prime_s 的时候就应该退出了
如果 i 的最小质因数是 Prime_j ，那么说明 i \times Prime_j 的最小质因数还是 Prime_j ，所以 j 本身还是符合筛条件的 -
i \times Prime_s 的最小质因数确实是 Prime_s
如果 i \times Prime_s 的最小质因数是 Prime_t ，那么 Prime_t 应当早就被枚举到，并且退出
所以， j 之前的数都符合筛条件 -
i \times Prime_b 的最小质因数一定是 Prime_j
因为 Prime_j 是 i 的最小质因数，所以 i \times Prime_b 的最小质因数一定是 Prime_j （因为是从小到大遍历，所以 Prime_b 肯定比 Prime_j 要大）
所以， j 之后的数都是不符合筛条件的
备注：
当 i 还不大时，一层循环内可能就筛去大量合数，看起来耗时较大
但它保证了合数只会被筛一次，当 i 不断接近 n 时，几乎不会筛什么数
时间复杂度是线性的
建议配合下面两篇证明使用更佳
正确性证明
设要筛掉的一合数 Z 的最小质因数为 p_z ，令 X=Z/p_z ，则一定有 p_x \ge p_z （否则 Z 的最小质因数为 p_x ），当外层循环 i = X 时，我们会从小到大枚举质数。由于 p_x \ge p_z ，所以在退出循环前，一定会枚举到 p_z ，也就是说 Z 肯定会被标记
核心： p_x 绝对不会小于 p_z
线性复杂度证明
注意这个算法一直使用“质数 \times 某数”的方式标记合数，又已知每个合数都能被最小质因数筛掉，所以我们唯一需要考虑的是这个数是否会被“另外质数 \times 另外某数 ”再筛一次来浪费时间。
设要筛掉的合数 Z 的最小质因数为 p_z ，再设这个万恶的质因数为 p_n ，令 Y=Z/p_n ，则 Y 中绝对有 p_z 这个因子，当外层 i==Y 时，它想要遍历到 p_n ，却在 j==p_z 时因为 i \mod p_z==0 而退出了。所以， Z 只能通过 p_z 筛掉
核心： Y 里绝对会有 p_z 这个因子
时间复杂度
O(n)
真的写了好久啊，求点赞QAQ