第89课：数论基础

所属模块：数学算法难度：intermediate 标签：gcd, lcm, prime, sieve 上一课：位运算枚举子集 下一课：模运算与快速幂

1. 学习目标

学完本课后，你将能够：

理解最大公约数 (GCD) 和最小公倍数 (LCM) 的概念，并掌握其高效计算方法。
掌握判断一个数是否为素数的算法。
理解并实现埃拉托斯特尼筛法，用于高效生成素数表。
将数论基础应用于解决常见的算法问题。

2. 核心概念

2.1 最大公约数 (Greatest Common Divisor, GCD)

通俗理解：想象你有两根长度分别为a和b的绳子，你想用一把尺子去量，要求必须整根量完。能同时整除a和b的最长尺子长度，就是a和b的最大公约数。

计算方法：最常用的是欧几里得算法（辗转相除法）。其核心思想非常简单：

两个整数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。数学表达：gcd(a, b) = gcd(b, a mod b)，直到b为0时，a就是最大公约数。

为什么有效：因为a mod b就是a除以b的余数，它包含了a和b共有的所有质因数，而移除了b的倍数部分，问题规模减小了。

2.2 最小公倍数 (Least Common Multiple, LCM)

通俗理解：继续上面的绳子例子。你现在要找一个长度，使得a米和b米长的绳子都能恰好量完这个长度，且这个长度是最短的。这个长度就是最小公倍数。

计算方法：一个非常重要的性质是：

两个数的乘积，等于它们最大公约数与最小公倍数的乘积。即：a * b = gcd(a, b) * lcm(a, b)。因此，lcm(a, b) = (a * b) / gcd(a, b)。

在编程时，为了避免乘法溢出，通常写成 a / gcd(a, b) * b。

2.3 素数 (Prime Number)

定义：一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数称为素数（或质数）。否则称为合数。

素数判定：判断一个数n是否为素数，最直接的方法是用2到sqrt(n)之间的所有整数去试除。

原理：如果n是合数，那么它一定可以分解为两个大于1的因子p和q（p <= q）。那么p必然小于等于sqrt(n)。
优化：只需检查奇数（除了2），或利用6k±1规律进一步优化。

2.4 埃拉托斯特尼筛法 (Sieve of Eratosthenes)

问题：如果需要找出N以内所有的素数，一个个判断会很慢（O(N√N)）。

思想：一个更聪明的方法是“筛”。从最小的素数2开始，把它的所有倍数（除了它本身）标记为合数。然后找下一个没被标记的数（它一定是素数），再把它的所有倍数标记掉。重复这个过程，直到筛完。剩下的未被标记的数就是素数。

效率：时间复杂度为O(N log log N)，空间复杂度O(N)，是生成大范围素数表的标准算法。

3. 代码示例

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// 辗转相除法求最大公约数 (GCD)
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 利用 GCD 求最小公倍数 (LCM)
long long lcm(long long a, long long b) {
    // 防止乘法溢出
    return a / gcd(a, b) * b;
}

// 判断单个数是否为素数 (试除法)
bool isPrime(long long n) {
    if (n <= 1) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false; // 排除偶数
    // 只检查奇数因子，且只需到 sqrt(n)
    for (long long i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 埃拉托斯特尼筛法生成素数表
vector<bool> sieveOfEratosthenes(int n) {
    // 创建一个布尔数组，初始都假设为素数 (true)
    vector<bool> is_prime(n + 1, true);
    // 0 和 1 不是素数
    is_prime[0] = is_prime[1] = false;

    // 从第一个素数2开始筛
    for (int p = 2; p * p <= n; ++p) {
        // 如果 p 是素数，则标记其所有倍数为合数
        if (is_prime[p]) {
            // 从 p*p 开始标记，因为更小的倍数已经被之前的素数标记过
            for (int i = p * p; i <= n; i += p) {
                is_prime[i] = false;
            }
        }
    }
    return is_prime;
}

int main() {
    // 测试 GCD 和 LCM
    long long a = 36, b = 48;
    cout << "GCD of " << a << " and " << b << " is: " << gcd(a, b) << endl; // 12
    cout << "LCM of " << a << " and " << b << " is: " << lcm(a, b) << endl; // 144

    // 测试素数判定
    cout << "Is 17 prime? " << (isPrime(17) ? "Yes" : "No") << endl; // Yes
    cout << "Is 91 prime? " << (isPrime(91) ? "Yes" : "No") << endl; // No (7*13)

    // 测试筛法
    int n = 50;
    vector<bool> primes = sieveOfEratosthenes(n);
    cout << "Primes up to " << n << ": ";
    for (int i = 2; i <= n; ++i) {
        if (primes[i]) cout << i << " ";
    }
    cout << endl; // 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

    return 0;
}

4. 实践练习

练习 1：基础应用 - 最大公约数与最小公倍数

编写一个程序，输入两个正整数a和b，输出它们的最大公约数和最小公倍数。

输入：36 48
预期输出：
```
GCD: 12
LCM: 144
```

练习 2：素数统计

编写一个程序，输入一个正整数n，输出2到n（包括n）之间素数的个数。

要求：分别用试除法和筛法两种方法实现，并比较它们处理n=1000000时的速度。
输入：30
预期输出（试除法）：10 (素数：2,3,5,7,11,13,17,19,23,29)

练习 3：筛法应用 - 素数间隙

输入一个正整数n，使用筛法找出2到n之间所有素数，并输出其中差值（相邻两个素数之差）最大的那个间隙值及其对应的两个素数。如果有多个相同最大间隙，输出第一对。

输入：100
预期输出：The maximum gap is 8, between primes 89 and 97.

5. 常见错误

辗转相除法递归实现导致栈溢出：对于极大数字，使用递归版本可能导致栈溢出。推荐使用循环实现。
```
// 递归版本 (可能栈溢出)
long long gcd_recursive(long long a, long long b) {
    return b == 0 ? a : gcd_recursive(b, a % b);
}
```
判断素数时循环条件写错：正确条件是 i * i <= n，而非 i <= sqrt(n)。因为sqrt计算开销大，且浮点数比较有精度风险。
```
// 错误写法
for (int i = 3; i <= sqrt(n); i += 2)
// 正确写法
for (int i = 3; i * i <= n; i += 2)
```
筛法中未排除0和1：在生成的is_prime数组中，必须显式将is_prime[0]和is_prime[1]设为false。
筛法倍数标记起点错误：标记p的倍数时，应从p*p开始，而不是2*p。因为2*p, 3*p等更小的倍数已经被之前更小的素数（如2，3）标记过了。
```
// 错误：从 2*p 开始标记，重复工作
for (int i = 2 * p; i <= n; i += p)
// 正确：从 p*p 开始
for (int i = p * p; i <= n; i += p)
```

计算LCM时发生溢出：a * b 可能超出long long范围。务必先除再乘。

// 错误写法 (可能溢出)
long long lcm = (a * b) / gcd(a, b);
// 正确写法
long long lcm = a / gcd(a, b) * b;

6. 小结

本课我们学习了数论中最基础且强大的几个工具：

最大公约数 (GCD)：通过高效的辗转相除法求解，是许多算法的基础。
最小公倍数 (LCM)：通过与 GCD 的关系 (LCM = a / GCD * b) 间接求得。
素数判定：基于试除法，理解O(√n)复杂度的来源。
埃拉托斯特尼筛法：生成大范围素数表的利器，时间复杂度O(N log log N)。

这些概念在密码学、组合数学、哈希函数设计以及各类算法竞赛题目中都有广泛应用。例如，计算组合数、求解线性同余方程等场景都离不开GCD。掌握它们，为你学习下一课的模运算与快速幂打下了坚实的基础。

练习编辑器

rust