当前位置：首页 > news >正文

【算法学习笔记】30：埃氏筛（Sieve of Eratosthenes）和线性筛（Linear Sieve）

news 来源：原创 2025/6/17 20:54:44

测试题目：AcWing 868. 筛质数

埃氏筛（Sieve of Eratosthenes）

如果 $i$ 是素数，每次把 $i$ 的倍数都筛掉，存在重复筛选，时间复杂度 $\cdot log(logn)$ 。

#include <iostream>using namespace std;const int N = 1e6 + 10;
int n, cnt = 0;
bool st[N]; // false as primeint main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (st[i]) continue;cnt ++ ;for (int j = i * 2; j <= n; j = j + i)st[j] = true;}cout << cnt << endl;return 0;
}

线性筛（Linear Sieve）

也叫欧拉筛，在埃氏筛的思想下，想办法让每个合数只被筛出去一次，消除重复筛选，这样时间复杂度就能降低到 $O (n)$ 。

为了让每个合数 $a$ 只被筛出去一次，由于我们是从小到大筛选质数的，因此可以考虑让这个合数 $a_1 \cdot a_2 \cdot ... \cdot a_k$ 由其最小的质因数 $a_1$ 筛掉。

因此每次遍历到一个数 $i$ ，不论是质数或者合数，其最小质因数如果是 $r$ ，那么由于我们从小到大筛到了 $i$ ，所以质数 $r$ 一定已经在目前的质数结果集里了（被筛好了）。

进而，所有 $< r$ 的质数都已经被筛好了，我们可以对于每个 $<= r$ 的质数 $x$ ，把 $\cdot i$ 筛掉，那么因为 $\cdot i$ 的最小质因数一定是 $x$ ，所以理应在（且仅在）这一轮被筛掉。

然而，知道每个数 $i$ 的最小质因数 $r$ 是困难的，但反正我们都要拿它每个 $<= r$ 的质数 $x$ 去筛掉 $\cdot i$ 了，每次筛掉之后看一下质数 $x$ 是不是 $i$ 的因数就可以了，因为我们是从小到大遍历质数 $x$ 的，所以 $x$ 第一次成为 $i$ 的因数的时候， $x$ 就是 $i$ 的最小质因数，这时候就可以停止筛了。

如果没有停止筛会有什么问题？重复筛选导致的算法退化！试想应在 $x$ 是 $i$ 的因子时停止，最后一轮筛掉的就是 $\cdot i$ ，如果没有停下来，又取了下一个质数 $x^{'}$ ，筛掉了 $\cdot i$ 。因为 $i$ 的最小质因数就是 $x$ ，所以 $\cdot i$ 这个数应该在先前就被质数 $x$ 以 $\cdot \frac{i \cdot x'}{x}$ 的模式筛过了！

写法上应该注意，线性筛不是像埃氏筛那样，只在发现质数的轮次筛合数，而是在每个轮次 $i$ ，不管最小质因数是 $r$ 的当前轮次 $i$ 是不是质数，都用 $<= r$ 的所有质数 $x$ 去筛 $\cdot i$ ，以保证每个数都仅被其最小质因数筛掉。

#include <iostream>using namespace std;const int N = 1e6 + 10;
int primes[N];
int n, cnt = 0;
bool st[N]; // false as primeint main()
{cin >> n;for (int i = 2; i <= n; i ++ ){if (!st[i]) primes[cnt ++ ] = i;for (int j = 0; primes[j] * i <= n; j ++ ){int x = primes[j];st[x * i] = true;if (i % x == 0) break;}}cout << cnt << endl;return 0;
}

埃氏筛（Sieve of Eratosthenes）

线性筛（Linear Sieve）

相关文章：