(4) 辗转相除法、素数表和唯一性定理

GESP C++五级官方考试大纲中，共有9条考点，本文针对第4条考点进行分析介绍。

（4）掌握辗转相除法（也称欧几里得算法）、素数表的埃氏筛法和线性筛法、唯一分解定理的原理和应用。 {: .prompt-info}

本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。 {: .prompt-warning}

五级其他考点回顾：

【GESP】C++五级考试大纲知识点梳理, (1) 初等数论
【GESP】C++五级考试大纲知识点梳理, (2) 模拟高精度计算
【GESP】C++五级考试大纲知识点梳理, (3-1) 链表-单链表
【GESP】C++五级考试大纲知识点梳理, (3-2) 链表-双向链表
【GESP】C++五级考试大纲知识点梳理, (3-3) 链表-单向循环链表
【GESP】C++五级考试大纲知识点梳理, (3-4) 链表-双向循环链表 {: .prompt-tip}

一、辗转相除法（欧几里得算法）

1.1 背景

该算法最早见于古希腊数学家欧几里得所著的《几何原本》（约公元前 300 年），是最早被记载的算法之一。中国古代也有类似的算法，称为更相减损术（《九章算术》）。它与欧几里得算法本质一致，只是用减法代替除法。这是已知最古老的算法之一，至今仍广泛使用。

1.2 主要用途

该算法最直接的用途是 求最大公约数（GCD），

1.3 算法原理

数学原理：

对于任意整数 $a$ 、 $b$ （假设 $a > b$ ），有：

\gcd(a, b) = \gcd(b, a \bmod b)

推理：

设 $d$ 是 $a$ 和 $b$ 的公约数，则 $d$ 也能整除 $a - kb$ （即余数）。
因此 $a$ 与 $b$ 的公约数集合，与 $b$ 和 $(a \bmod b)$ 的公约数集合相同。
所以 $\gcd(a,b) = \gcd(b, a \bmod b)$ 。
因此，可通过不断的递归用余数代替被除数将数缩小，直到余数 = 0为止，得到最大公约数 $b$ 。

算法步骤：

给定 $a$ , $b$ ( $a \geq b > 0$ )。
计算余数 $r = a \bmod b$ 。
若 $r = 0$ ，则 $\gcd = b$ ；否则令 $a \leftarrow b$ , $b \leftarrow r$ ，重复步骤 2。

例如：

求 $\gcd(252, 105)$ ：

$252 \div 105 = 2 \cdots 42 \rightarrow \gcd(252,105) = \gcd(105,42)$
$105 \div 42 = 2 \cdots 21 \rightarrow \gcd(105,42) = \gcd(42,21)$
$42 \div 21 = 2 \cdots 0 \rightarrow \gcd(42,21) = 21$

所以结果：21。

1.4 算法代码示例

/**
 * 求两个数的最大公约数(约定 a > b)
 * @param a 第一个数
 * @param b 第二个数
 * @return 最大公约数
 */
int gcd(int a, int b) {
    // 当b不为0时，继续循环
    while (b != 0) {
        // 保存b的值，因为下一步b会被修改
        int temp = b;
        // 将a除以b的余数赋给b
        b = a % b;
        // 将原来的b值赋给a
        a = temp;
    }
    // 当b为0时，a即为最大公约数
    return a;
}

辗转相除法的时间复杂度分析：

对于两个数 $a$ 和 $b$ ，每次迭代 $b$ 都会减小到原来的一半以下。因此，迭代次数不会超过 $\log_2(\max(a,b))$ 。

所以辗转相除法的时间复杂度为 $O(\log n)$ ，其中 $n$ 为输入数字的较大值。这也是为什么辗转相除法能够高效地求最大公约数。

实际上C++17在<numeric>头文件中内置了求最大公约数的函数std::gcd()，可以直接调用。例如：std::gcd(252, 105)将返回21。需要注意的是，该函数要求参数为非负整数。 {: .prompt-tip}

二、素数表的埃氏筛法（Eratosthenes）

2.1 背景

埃氏筛法由古希腊数学家 Eratosthenes of Cyrene 提出，他是一位著名的数学家、地理学家、天文学家和诗人，是亚历山大图书馆的馆长。该方法最早在 2 世纪的 Nicomachus of Gerasa 的著作 《Introduction to Arithmetic》 中首次提到，并归功于 Eratosthenes 。

2.2 主要用途

埃氏筛法最直接且广泛的应用是生成指定范围内的所有素数（素数表）――只需给定上限 $n$ ，即可高效找出所有小于或等于 $n$ 的素数。因其简单直观，常作为编程竞赛与算法课的入门示例。

2.3 算法原理

埃氏筛法背后的数学原理依赖两个关键定理（感兴趣了解，不感情的可跳过）：

定理 A：每个大于 1 的整数都有一个素数因子。 {: .prompt-info}

证明：设整数 $n \gt 1$ 且不含素因子。假设 $n$ 是最小的此类数。由于 $n$ 是合数，存在分解 $n = ab$ 其中 $1 \lt a, b \lt n$ 。根据 $n$ 的最小性， $a$ 必有素因子 $p$ 。因此 $p$ 也是 $n$ 的素因子，这与假设矛盾。故每个大于 1 的整数必有素数因子。

定理 B：若 $n$ 是合数，则它有一个素数因子 $\leq \sqrt{n}$ {: .prompt-info}

证明：若 $n=ab$ ，且假设 $a$ , $b$ 都大于 $\sqrt{n}$ ，则 $ab > n$ ，矛盾。因此至少有一个因子不大于 $\sqrt{n}$ ，因其本身或其素因子是 $n$ 的素因子，所以该因子 ≤ $\sqrt{n}$ 。

运用这两条定理，埃氏筛法可筛出所有素数：

构造：把从 2 到 $n$ 的所有整数列出。
筛法：
- 从最小的未标记数 2 开始，将它的所有倍数（大于 2 的）标记为合数。
- 找下一个未标记数 p，将它的倍数标记。
- 重复直到当前 p 超过 $\sqrt{n}$ 。

2.4 算法代码示例

创建 $2$ 到 $n$ 的布尔数组，初始设为全为“素数”。
对 $p$ $p$ 从 2 到 $\sqrt{n}$ $n$ ：
- 若 $p$ 未被标记，标记从 $p^2$ 、 $p^2 + p$ 、… ≤ $n$ 的所有数为“非素数”。
最终数组中未被标记的数就是素数。

vector<int> eratosthenes(int n) {
    // 创建一个布尔数组标记素数，初始假设所有数都是素数
    vector<bool> isPrime(n + 1, true);
    
    // 0和1不是素数，标记为false
    isPrime[0] = isPrime[1] = false;
    
    // 从2开始遍历到sqrt(n)
    for (int i = 2; i * i <= n; i++) {
        // 如果i是素数
        if (isPrime[i]) {
            // 将i的所有倍数标记为非素数(从i*i开始是因为更小的倍数已经被更小的素数标记过了。例如:对于i=5,5*2、5*3、5*4已经分别被2和3标记过)
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    // 创建存储素数的数组
    vector<int> primes;
    // 遍历标记数组，收集所有素数
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }
    return primes;
}

举例：n=30：

从 $2$ 开始，划去 $2$ 的倍数： $4, 6, 8, \ldots$
找下一个未划去的数 $3$ ，划去其倍数： $9, 12, \ldots$
再找下一个未划去的数 $5$ ，划去其倍数： $25, \ldots$
继续，直到 $\sqrt{n}$ 。
最后留下的数： $2,3,5,7,11,13,17,19,23,29$ 。

埃氏筛法的时间复杂度分析：

对于每个素数 $p$ ，需要标记其倍数 $2p, 3p, ..., \lfloor \frac{n}{p} \rfloor p$ 。

对于素数 2，需要标记 $\frac{n}{2}$ 次
对于素数 3，需要标记 $\frac{n}{3}$ 次
对于素数 5，需要标记 $\frac{n}{5}$ 次
…

总标记次数为： $n(\frac{1}{2} + \frac{1}{3} + \frac{1}{5} + ...)$

根据素数倒数和的性质，括号内的和约等于 $\log \log n$ 。

因此埃氏筛法的时间复杂度为 $O(n \log \log n)$ 。

空间复杂度为 $O(n)$ ，需要一个长度为 n 的布尔数组来标记数的状态。

三、素数表的线性筛法（欧拉筛法）

3.1 背景

线性筛（也称欧拉筛）是为了解决埃氏筛重复标记问题而提出的一种更加高效的方法。它最早在 1978 年由 David Gries 和 Jayadev Misra 在《Communications of the ACM》上提出，将素数筛选的时间复杂度优化至 $O(n)$ 。

3.2 主要用途

高效生成素数表：在线性时间内生成 2～n 内所有素数，比埃氏筛省去冗余标记，非常适合大规模运算场景。

3.3 算法原理

线性筛的关键思想是：

每个合数只被其最小质因子筛一次，避免重复标记，保证整体复杂度为 $O(n)$ 。 {: .prompt-info}

可以这样理解：

对于任意合数 $n$ ，它一定可以表示为 $n = p \times i$ ，其中 $p$ 是 $n$ 的最小质因子， $i$ 是某个整数。
线性筛通过控制标记时机，确保每个合数 $n$ 只在遍历到 $i$ 且使用其对应的最小质因子 $p$ 时被标记一次。
这种机制避免了埃氏筛中同一个数被多个不同质因子重复标记的情况。例如 12 在埃氏筛中会被 2、3 都标记一次，而在线性筛中只在 $i=6$ , $p=2$ 时被标记。

{: .prompt-info}

这样就能确保每个合数只被其最小质因子标记一次，从而使筛选过程线性。

3.4 算法代码示例

代码实现核心步骤如下：

维护素数表与标记表：使用数组 is_prime[i] 判断是否为素数，以及动态保存的素数列表 primes。
从小到大遍历：遍历 $i$ $i$ 从 $2$ $2$ 到 $n$ $n$ ：
- 若 is_prime[i] 为真，说明 $i$ 是素数，加入 primes。
筛合数并断点：对每个当前素数 $p$ $p$ ：
- 标记 $i \times p$ 为合数。
- 若 $p$ 整除 $i$ （意味着 $p$ 是 $i$ 的最小质因子），跳出当前素数循环，保证 $i \times p$ 不被其他更大的素数再次筛。

// 设置筛选范围的上限，根据n的范围调整
const int MAXN = 1000000;
// 存储找到的素数
vector<int> primes;
// 标记数组，初始假设所有数都是素数
vector<bool> is_prime(MAXN + 1, true);

/**
 * 线性筛法求素数
 * @param n 筛选范围上限
 */
void linear_sieve(int n) {
    // 0和1不是素数，标记为false
    is_prime[0] = is_prime[1] = false;
    // 从2开始遍历到n
    for (int i = 2; i <= n; i++) {
        // 如果i是素数，加入素数数组
        if (is_prime[i]) {
            primes.push_back(i);
        }
        // 用已知的素数去筛合数
        for (int p : primes) {
            // 计算i和素数p的乘积，用long long避免溢出
            long long x = 1LL * i * p;
            // 如果超出范围则退出当前循环
            if (x > n) {
                break;
            }
            // 标记i*p为合数
            is_prime[x] = false;
            // 如果i能被p整除，说明p是i的最小质因子，退出循环
            // 这样保证每个合数只会被其最小质因子筛掉一次
            if (i % p == 0) {
                break;  // 保证唯一筛标记
            }
        }
    }
}

以 $n=30$ 为例，线性筛的执行过程如下：

初始化：
- is_prime[0] = is_prime[1] = false
- primes = []（空数组）
- 其他位置 is_prime 全为 true
$i = 2$
- $2$ 是素数，加入 primes：primes = [2]
- 标记 $2 \times 2 = 4$ 为合数
$i = 3$
- $3$ 是素数，加入 primes：primes = [2,3]
- 标记 $3 \times 2 = 6$ 为合数
- 标记 $3 \times 3 = 9$ 为合数
$i = 4$
- $4$ 不是素数（已被标记）
- 标记 $4 \times 2 = 8$ 为合数
- $4 \div 2 = 2$ 整除，break
$i = 5$
- $5$ 是素数，加入 primes：primes = [2,3,5]
- 标记 $5 \times 2 = 10$ 为合数
- 标记 $5 \times 3 = 15$ 为合数
- 标记 $5 \times 5 = 25$ 为合数

以此类推…最终得到 $30$ 以内的素数： $2,3,5,7,11,13,17,19,23,29$

关键特点：

每个合数仅被其最小质因子 $p$ 筛掉一次
例如对于 $12$ ，只在 $i=6,p=2$ 时被标记为合数，而不会在 $i=4,p=3$ 时重复标记
这种非重复标记机制保证了算法的线性时间复杂度 $O(n)$

3.5 小结：埃氏筛 vs. 线性筛

特性	埃氏筛	线性筛
标记次数	每个素数标记其所有倍数，可能重复标记	每个合数由最小质因子标记一次，无重复
时间复杂度	$O(n \log \log n)$	$O(n)$
代码实现	简单直观	略复杂但更高效

{% include custom/custom-post-content-inner.html %}

四、唯一分解定理

4.1 背景

唯一分解定理，最早由古希腊著名数学家欧几里得（Euclid）在《几何原本》中提出相关命题，多个命题合并为定理雏形。《几何原本》中涉及欧几里得引理（Euclid’s Lemma）、每个大于 1 的数都有素数因子以及分解的存在性等基本观点构成了唯一分解定理的基础。

波斯数学家 al-Fārisī 曾明确提出每个整数皆可素数分解，但并未证明唯一性。

现代数学中，卡尔·高斯（Carl Friedrich Gauss）在其 1801 年作品《算术研究》（Disquisitiones Arithmeticae）中首次系统地提出并证明了该定理，奠定其严格数学地位。

4.2 定理内容概述

存在性：每个大于 1 的整数，要么是素数，要么可以表示为若干素数的乘积。 唯一性：这样的表达方式（乘积中素数的个数与类型）除了排列顺序外，是唯一确定的。 {: .prompt-info}

例如:

1200 = 2^4 \times 3^1 \times 5^2

无论如何分解，都会得到这 3 个素数，幂次也一定是 4、1 和 2，无其他组合。

4.3 证明思路概述（存在性 + 唯一性）

4.3.1 存在性：归纳法

以数学归纳法为基础：

基础：当 $n = 2$ 时显然成立，因为 2 是素数本身。
归纳步骤：
- 假设对所有小于 $k$ 的整数成立。
- 若 $k$ 是素数，直接成立；若不是，则存在 $1 < a, b < k$ ，使 $k = a \times b$ 。由归纳假设， $a$ 、 $b$ 都可以分解成素因子，从而 $k$ 也一样。

4.3.2 唯一性：借助欧几里得引理（Euclid’s Lemma）

欧几里得引理：若素数 $p$ 整除 $a \times b$ ，则必定整除 $a$ 或 $b$ 。 {: .prompt-info}

证明要点：

假设存在两种不同的素因子分解：
$n = p_1 p_2 \cdots p_k = q_1 q_2 \cdots q_l$
使用欧几里得引理推导： $p_1$ 必定整除右边某个 $q_j$ ，但两者皆为素数，故 $p_1 = q_j$ 。可通过交换整理得到对应的顺序相同。
消去一项后继续对剩余部分应用同样逻辑，直至全部素数因子一一对应，说明两种分解必定是相同的（仅顺序可能不同）。

4.4 应用示例

示例：

360 = 2^3 \cdot 3^2 \cdot 5^1

任何素数分解方式都必包含这三个素数，并且幂次与该表达一致。

应用：

计算最大公约数：

\gcd(a, b) = \prod p_i^{\min(\alpha_i, \beta_i)}

计算最小公倍数：

\mathrm{lcm}(a, b) = \prod p_i^{\max(\alpha_i, \beta_i)}

其中 $a = \prod p_i^{\alpha_i}, b = \prod p_i^{\beta_i}$ 是分解后的表达。

例如： 计算 360 和 1200 的最大公约数和最小公倍数：

首先分解质因数：

360 = 2^3 \times 3^2 \times 5^1

1200 = 2^4 \times 3^1 \times 5^2

根据公式：

最大公约数取每个质因数的最小幂次：

\gcd(360, 1200) = 2^3 \times 3^1 \times 5^1 = 120

最小公倍数取每个质因数的最大幂次：

\mathrm{lcm}(360, 1200) = 2^4 \times 3^2 \times 5^2 = 3600

可以验证： $360 \times 1200 = \gcd(360, 1200) \times \mathrm{lcm}(360, 1200)$

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号

Last updated on 2025年8月30日

(3-4) 链表-双向循环链表