线性筛

一句话算法

线性筛用“最小质因子”筛合数，保证每个合数只被标记一次。

问题模型

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

普通埃氏筛已经足够快，但一个合数可能被多个质因子重复标记。线性筛进一步规定：每个合数只由它的最小质因子生成一次。

核心直觉

任意合数 $x$ 都可以唯一写成：

其中 $p$ 是 $x$ 的最小质因子。

线性筛枚举 $i$，再用已经找到的素数 $p$ 去生成 $i\times p$。当发现 i % p == 0 时，说明 $p$ 已经是 $i$ 的最小质因子。如果继续使用更大的素数 $p'$，那么 $i\times p'$ 的最小质因子仍然来自 $i$，不是 $p'$，会造成重复标记，所以必须 break。

算法步骤

1. 从小到大枚举 i = 2..n。
2. 如果 i 还没有被标记为合数，说明 i 是素数，加入 primes。
3. 依次枚举已经得到的素数 p：
   • 如果 i * p > n，停止；
   • 标记 i * p 为合数；
   • 记录 i * p 的最小质因子为 p；
   • 如果 i % p == 0，停止枚举更大的素数。

算法证明

关键不变量： 每个被标记的合数 $x=i\times p$，都由它的最小质因子 $p$ 标记。

1. 不会漏

   任取合数 $x$，令 $p$ 为 $x$ 的最小质因子，令 $i=x/p$。当外层枚举到 $i$ 时，$p$ 已经在素数表中。因为 $p$ 是 $x$ 的最小质因子，所以 $p$ 不大于 $i$ 的最小质因子，内层会枚举到 $p$ 并标记 $x$。

2. 不会重

   如果某个合数 $x$ 被两次标记，设两次使用的素数分别是 $p_1,p_2$。根据不变量，二者都必须是 $x$ 的最小质因子。最小质因子唯一，所以 $p_1=p_2$，对应的 $i=x/p$ 也唯一，矛盾。

3. break 的必要性

   当 i % p == 0 时，$p$ 是 $i$ 的最小质因子。若继续枚举更大的素数 $q$，则 $i\times q$ 的最小质因子仍然是 $p$，不应该由 $q$ 标记。因此必须停止。

所以每个合数只被标记一次，算法正确。

复杂度分析

每个合数只被标记一次，每个素数只被加入一次，因此总时间复杂度为 $O(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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

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

struct LinearSieve {
    vector<int> primes;
    vector<int> min_factor;
    vector<bool> is_composite;

    void build(int n) {
        primes.clear();
        min_factor.assign(n + 1, 0);
        is_composite.assign(n + 1, false);

        for (int i = 2; i <= n; i++) {
            if (!is_composite[i]) {
                primes.push_back(i);
                min_factor[i] = i;
            }

            for (int p : primes) {
                if (p > n / i) break;
                int x = i * p;
                is_composite[x] = true;
                min_factor[x] = p;

                // p 是 i 的最小质因子时，不能再用更大的质数去生成 i*p'。
                if (i % p == 0) break;
            }
        }
    }

    bool is_prime(int x) const {
        return x >= 2 && !is_composite[x];
    }
};

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

    int n;
    cin >> n;

    LinearSieve sieve;
    sieve.build(n);

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

    return 0;
}
    

测试用例

输入：

30

输出：

2 3 5 7 11 13 17 19 23 29

应用分类详解

线性筛的本质是按最小质因子给每个整数建立唯一生成关系。

一、素数表预处理

典型模式： 多次判断素数，或需要枚举 $1..n$ 内全部素数。

识别信号： 出现“多次询问素数”“输出所有素数”“预处理质数表”。

核心建模： 先筛出素数表，后续查询直接查标记或遍历 primes。

二、最小质因子预处理

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

识别信号： 多次分解、约数统计、质因子个数统计。

核心建模： 在线性筛中记录 min_factor[x]，分解时不断除以最小质因子。

三、积性函数线性递推

典型模式： 需要求 $1..n$ 中每个数的欧拉函数、莫比乌斯函数等。

识别信号： 出现“欧拉函数表”“莫比乌斯函数”“所有数的约数个数”。

核心建模： 利用 i % p == 0 与否区分“新增质因子”和“已有质因子次数增加”。

经典例题

1. luogu-P3383

素数筛模板题。线性筛可以在 $O(n)$ 内得到素数表，并支持后续多次查询。

2. 多次质因数分解

如果题目要分解很多个不超过 $n$ 的数，可以在线性筛中记录每个数的最小质因子，之后用 min_factor 快速拆分。

3. 欧拉函数表

线性筛不仅能筛素数，还能同步递推积性函数。求所有 $\varphi(i)$ 时，关键分类是 i % p == 0 与否。

参考

• 埃氏筛
• 欧拉筛