我的算法书 - 素数判定与素数筛

一句话算法

单个数用“不超过平方根的因子”判断，大范围素数用“把合数批量划掉”的筛法预处理。

问题模型

素数是只有两个正因数的正整数： $1$ 和它本身。合数是大于 $1$ 且不是素数的整数。

在算法竞赛中，素数通常对应三类需求：

判断一个数 n 是否为素数。
求出 1..n 中所有素数。
预处理素数表，给质因数分解、欧拉函数、莫比乌斯函数等数论算法使用。

“素数与合数”

$n>1$ 且只有 $1,n$ 两个正因数时， $n$ 是素数。 $n>1$ 且存在非平凡分解 $n=a\times b$ 时， $n$ 是合数。

核心直觉

判断单个数时，不需要枚举到 n-1。如果：

n=a\times b,\quad 1<a\le b<n

那么一定有：

a\le \sqrt n

所以只要在 $[2,\sqrt n]$ 中找不到任何因子， $n$ 就不可能是合数，只能是素数。

当需要处理一整段 1..n 时，逐个试除会重复做很多工作。筛法换了一个角度：不去问“每个数是不是素数”，而是从已经确定的素数出发，把它的倍数全部标成合数。

2 是素数 -> 4, 6, 8, 10, ... 都是合数
3 是素数 -> 6, 9, 12, 15, ... 都是合数
5 是素数 -> 10, 15, 20, 25, ... 都是合数

算法步骤

试除法

若 n < 2，不是素数。
特判 2 是素数。
若 n 是大于 2 的偶数，不是素数。
枚举奇数因子 d = 3,5,7,...，直到 d*d > n。
若存在 n mod d == 0，则 n 是合数；否则是素数。

埃氏筛

建立 is_composite[0..n]，表示某个数是否已经被标为合数。
从 2 枚举到 n。
若 i 没有被标记，则 i 是素数。
从 i*i 开始，把 i 的倍数标记为合数。

从 i*i 开始是因为 2*i,3*i,...,(i-1)*i 已经被更小的因子筛过。

线性筛

埃氏筛中，一个合数可能被多个素因子重复标记。例如 12 会被 2 标记，也会被 3 标记。

线性筛的目标是：

每个合数只被它的最小质因子筛掉一次。

做法是从小到大枚举 i，再枚举已经找到的素数 p，标记 i*p。一旦发现 i mod p == 0，立刻停止枚举更大的素数。

这个 break 是线性筛的核心。

算法证明

试除法为什么只到平方根

若 $n$ 是合数，则存在：

n=a\times b,\quad 1<a\le b<n

假设 $a>\sqrt n$ ，因为 $b\ge a$ ，所以：

n=a\times b>a\times a>n

矛盾。因此 $a\le\sqrt n$ 。

所以合数一定有一个不超过 $\sqrt n$ 的非平凡因子。反过来，如果 $[2,\sqrt n]$ 中没有任何因子， $n$ 就不是合数，也就是素数。

埃氏筛为什么不漏

任意合数 $x$ 都有一个最小质因子 $p$ 。设：

x=p\times q

因为 $p$ 是最小质因子，所以 $q\ge p$ ，于是：

x\ge p^2

当筛法枚举到 $p$ 时，会从 $p^2$ 开始筛掉 $p$ 的所有倍数，因此一定会筛到 $x$ 。素数没有非平凡因子，所以不会被任何更小的数筛掉。

线性筛为什么不重

设 $L(x)$ 表示合数 $x$ 的最小质因子。线性筛希望只用这一种方式筛掉 $x$ ：

x = \frac{x}{L(x)} \times L(x)

当外层枚举到 i，内层按从小到大的顺序枚举素数 p。

若 i mod p != 0，说明 p 小于 i 的所有质因子，所以 p 是 i*p 的最小质因子，可以标记。
若 i mod p == 0，说明 p 是 i 的最小质因子。此时 i*p 可以标记，但继续枚举更大的素数 p' 时，i*p' 的最小质因子仍然是 p，不是 p'，所以必须停止。

因此每个合数都只会在“最小质因子”对应的那一次被标记，筛法总标记次数是 $O(n)$ 级别。

复杂度分析

方法	适用场景	时间复杂度	空间复杂度
试除法	单次判断素数	$O(\sqrt n)$	$O(1)$
埃氏筛	求 `1..n` 的素数表	$O(n\log\log n)$	$O(n)$
线性筛	求素数表，并为积性函数预处理打基础	$O(n)$	$O(n)$

如果只判断一两个大数，试除法最简单；如果要回答很多次素数查询，应该先筛一张表。

代码实现

试除法判定素数

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

bool is_prime(long long n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;

    for (long long d = 3; d <= n / d; d += 2) {
        if (n % d == 0) return false;
    }
    return true;
}

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

    long long n;
    cin >> n;
    cout << (is_prime(n) ? "YES" : "NO") << '\n';
    return 0;
}

埃氏筛

cpp

        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;
}

线性筛

cpp

        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;
}

测试用例

单个素数判断

输入：

输出：

YES

输入：

输出：

NO

筛出 `1..20` 的所有素数

输入：

输出：

2 3 5 7 11 13 17 19

应用分类详解

素数算法的本质是处理“整数是否能被拆成更小因子”的问题。看到因子、倍数、整除、质因数分解、模素数时，都应该想到素数预处理。

一、单次素数判定

典型模式： 题目只询问少量几个数是否为素数。

识别信号： 输入规模不大，或者 n 很大但查询次数很少。

核心建模： 枚举不超过 $\sqrt n$ 的因子，一旦找到因子就判为合数。

应用场景	经典题目	核心思路
判断素数	素数判定模板题	试除到平方根
判断回文素数	Luogu P1217	先生成候选数，再做素数判定
判断特殊质数	Luogu P1304	枚举拆分并判断两边是否为素数

二、素数表预处理

典型模式： 多次查询 x 是否为素数，或需要输出一段范围内的所有素数。

识别信号： 出现“多次询问”“求 1..n 中所有素数”“统计素数个数”。

核心建模： 一次筛出 is_composite 和 primes，之后查询 $O(1)$ ，枚举按素数表顺序进行。

应用场景	经典题目	核心思路
素数筛模板	Luogu P3383	预处理素数表后回答第 $k$ 个素数
区间内素数统计	数论基础题	先筛再做前缀和
多次素数查询	素数查询模板题	`!is_composite[x]` 直接判断

三、质因数分解加速

典型模式： 要分解很多个数，或者统计约数个数、约数和。

识别信号： 题面出现“质因数”“约数个数”“最大质因子”“分解质因数”。

核心建模： 先筛出不超过 $\sqrt n$ 的素数，再用这些素数试除；如果用了线性筛的 min_factor，还可以按最小质因子不断拆分。

应用场景	经典题目	核心思路
质因数分解	分解质因数模板题	用素数表减少无效试除
约数个数	数论计数题	分解后使用指数乘法公式
最大质因子	质因子统计题	分解过程中更新最大素因子

四、数论函数预处理

典型模式： 要同时计算很多个数的欧拉函数、莫比乌斯函数或最小质因子。

识别信号： 出现“欧拉函数表”“莫比乌斯函数”“积性函数”“线性时间预处理”。

核心建模： 线性筛在标记 i*p 的时候知道 p 是否整除 i，这正好可以推出积性函数的递推式。

应用场景	经典题目	核心思路
欧拉函数表	欧拉函数预处理题	在线性筛中递推 $\varphi$
莫比乌斯函数	莫比乌斯函数模板题	根据是否含平方因子递推
最小质因子表	快速分解多个数	`min_factor[x]` 反复拆分

经典例题

1. Luogu P3383 【模板】线性筛素数

要求预处理素数并回答第 $k$ 个素数。重点是写对线性筛的 break，并保证数组范围足够。

2. Luogu P1217 回文质数

要求输出区间内的回文素数。直接枚举所有数会慢，可以先生成回文数，再使用试除法或筛法判断素数。

3. Luogu P1304 哥德巴赫猜想

对每个偶数枚举拆分 x = p + q，用筛法快速判断 p 和 q 是否为素数。

参考

本书埃氏筛章节：math/numherTheory/Eratosthenes.md
本书线性筛章节：math/numherTheory/线性筛/index.md

一句话算法

问题模型

核心直觉

算法步骤

试除法

埃氏筛

线性筛

算法证明

试除法为什么只到平方根

埃氏筛为什么不漏

线性筛为什么不重

复杂度分析

代码实现

试除法判定素数

埃氏筛

线性筛

测试用例

单个素数判断

筛出 1..20 的所有素数

应用分类详解

一、单次素数判定

二、素数表预处理

三、质因数分解加速

四、数论函数预处理

经典例题

1. Luogu P3383 【模板】线性筛素数

2. Luogu P1217 回文质数

3. Luogu P1304 哥德巴赫猜想

参考

筛出 `1..20` 的所有素数