埃氏筛

一句话算法

埃氏筛不逐个判断素数，而是从小素数开始，把它的倍数全部标成合数。

问题模型

给定整数 n，求出 1..n 中所有素数。

朴素做法是对每个数试除，整体复杂度较高。埃氏筛利用“合数一定有素因子”这一点，批量删除合数。

核心直觉

如果 i 是素数，那么：

2i, 3i, 4i, ...

一定都不是素数。

所以从 2 开始，如果一个数还没有被筛掉，它就是素数；然后用它去筛掉后面的倍数。

以 n=20 为例：

初始: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
筛 2: 删除 4 6 8 10 12 14 16 18 20
筛 3: 删除 9 15
筛 5: 从 25 开始，已经超过 20
剩下: 2 3 5 7 11 13 17 19

为什么从 i * i 开始筛

筛 i 的倍数时，小于 i*i 的倍数形如：

2*i, 3*i, ..., (i-1)*i

这些数已经在筛 2,3,...,i-1 的时候被处理过了。

因此从 i*i 开始即可。

为了避免 i*i 溢出，模板里通常先判断：

        
1

        if (i > n / i) continue;
    

算法步骤

1. 建立 is_composite 数组，初始全为 false。
2. 枚举 i = 2..n。
3. 如果 is_composite[i] == false，说明 i 是素数，加入素数列表。
4. 若 i*i <= n，从 i*i 开始，每次加 i，把这些倍数标为合数。
5. 枚举结束后，列表中就是所有素数。

算法证明

核心不变量：当枚举到 i 时，所有小于 i 的合数都已经被筛掉。

如果 i 没有被筛掉，假设它是合数，那么它一定有一个小于 i 的素因子 p。枚举到 p 时，i 作为 p 的倍数应该已经被筛掉，矛盾。因此 i 是素数。

对于任意合数 x，设它的最小素因子为 p，则 x = p * q 且 q >= p，所以 x >= p*p。当枚举到 p 时，内层循环从 p*p 开始，会筛到 x。

因此算法最终筛掉所有合数，留下所有素数。

复杂度分析

• 时间复杂度：$O(n\log\log n)$。
• 空间复杂度：$O(n)$。

埃氏筛比逐个试除快很多，但同一个合数可能被多个素因子重复标记。如果需要严格线性复杂度，可以学习欧拉筛。

代码实现

        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

        #include <bits/stdc++.h>
using namespace std;

vector<int> eratosthenes(int n) {
    vector<bool> is_composite(n + 1, false);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (is_composite[i]) continue;

        primes.push_back(i);
        if (i > n / i) continue;

        for (int j = i * i; j <= n; j += i) {
            is_composite[j] = true;
        }
    }

    return primes;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    auto primes = eratosthenes(n);
    for (int i = 0; i < (int)primes.size(); i++) {
        if (i) cout << ' ';
        cout << primes[i];
    }
    cout << '\n';

    return 0;
}
    

测试用例

输入：

20

输出：

2 3 5 7 11 13 17 19

应用分类详解

埃氏筛的本质是批量预处理素数。只要后续会频繁判断素数、枚举素数或处理质因子，就应该先考虑筛法。

一、素数表预处理

典型模式： 多次询问某个数是否为素数，或需要枚举所有素数。

识别信号： 出现“多次查询素数”“输出范围内所有素数”。

核心建模： 一次筛出素数表，后续 $O(1)$ 判断或顺序枚举。

二、质因数分解加速

典型模式： 要分解很多个数。

识别信号： 出现“多个数质因数分解”“约数个数”“约数和”。

核心建模： 先筛出不超过 $\sqrt n$ 的素数，再用素数表试除。

三、作为数论算法前置

典型模式： 后续算法依赖素数列表。

识别信号： 出现“欧拉函数”“莫比乌斯函数”“线性筛”“质数枚举”。

核心建模： 埃氏筛提供基础素数表；更高级的积性函数通常使用线性筛。

经典例题

1. 素数筛模板题

练习输出 1..n 中所有素数，重点是写对 i*i 起点和溢出判断。

2. 多次素数询问题

先用埃氏筛预处理，再回答每个数是否为素数。

3. 质因数分解批处理

先筛出素数表，再用素数表对每个数做试除分解。

参考

• 本书线性筛章节：math/numherTheory/线性筛/index.md