第 54 章数字的奥秘——初等数论

🏗️ 前情回顾：第 53 章你用指针把节点串成了链表，体会了"结构"的力量。这一章我们换一个完全不同的方向——回到数字本身。之前你学过加减乘除、取余运算符 %、循环和判断。这些工具组合起来，能撬开数字世界的许多秘密：怎么快速判断一个数是不是质数？一个数有多少个约数？RSA 加密为什么被认为是安全的？答案就在本章——初等数论。

🎯 本章目标

学完这一章，你能：

判断一个整数是否整除另一个整数
用试除法（O(√n)）判断一个数是否为质数
对一个整数进行质因数分解
用"成对出现"的技巧枚举一个数的所有约数
理解模运算 % 的基本性质并灵活运用
理解同余的概念
快速判定闰年等数论小技巧

📖 故事引入

秘密的配方

公元前 400 年，斯巴达将军用一根木棍和一条皮带传递军事密令——这就是最早的"加密"之一。两千年后，RSA 加密算法的发明者利用了这样一个简单事实：把两个大质数相乘很容易，但给你它们的乘积，想找回原来的两个质数却极其困难。

比如：23 × 41 = 943，大家一眼就能算出来。但如果我说"有一个数 999999937 × 1000000007 等于多少？"——你用计算器乘出来很快。反过来，"999999944000000259 是哪两个质数的乘积？"——你试试看。

现代互联网的安全通信（HTTPS、数字签名）就建立在这个"单向容易、反向极难"的数学事实之上。

顺着这个故事的线索，我们需要从最基础的"整除"开始，一步步揭开数字的奥秘。

🧱 知识讲解

54.1 整除与约数

整数 a 除以非零整数 b，如果余数为 0，就说 b 整除 a，记作 b | a。此时：

b 是 a 的约数（也叫因数、因子）
a 是 b 的倍数

cpp

// 判断 b 是否整除 a
bool divides(int b, int a) {
    return a % b == 0;   // 余数为 0 → 整除
}

divides(3, 12);   // true  → 3 整除 12
divides(5, 12);   // false → 5 不整除 12

约数的几个基本性质（无需证明，想一想就明白）：

1 是任何正整数的约数
每个正整数 a 本身也是 a 的约数
如果 b | a，且 a ≠ 0，则 |b| ≤ |a|
如果 b | a 且 c | b，则 c | a（传递性）

📝 注意：数论中的"约数"通常讨论正整数范围，除非特别说明。

54.2 质数：只能被 1 和自身整除的数

质数（素数）：大于 1，且只被 1 和它自身整除的正整数。例如 2, 3, 5, 7, 11, 13, …

合数：大于 1 且不是质数的正整数。例如 4, 6, 8, 9, 10, …

1 既不是质数也不是合数——它是"单位元"。

试除法判断质数：O(√n)

判断 n 是不是质数，最直接的想法：用 2 到 n-1 每个数试除一遍。但如果 n 是合数，它一定有一个不超过 √n 的因子——为什么？因为如果 a×b=n 且 a≤b，那么 a²≤a×b=n，所以 a≤√n。

因此只需要试除到 √n 就行：

cpp

bool isPrime(int n) {
    if (n <= 1) return false;          // 1 不是质数
    if (n == 2) return true;           // 2 是最小的质数
    if (n % 2 == 0) return false;      // 偶数（除了 2）都不是质数

    for (int i = 3; i * i <= n; i += 2) {  // 只需试奇数，到 √n 即可
        if (n % i == 0) return false;
    }
    return true;
}

复杂度：从 O(n) 降到了 O(√n)。判断 10¹² 以内的数，√n 大约是 10⁶ —— 百万次循环，肉眼可见地快。

💡 i * i <= n 等价于 i <= sqrt(n)，但避免了浮点数运算。注意当 n 很大时 i * i 可能溢出 int，竞赛中改写成 for (long long i = 3; i*i <= n; i += 2)。

54.3 质因数分解：把合数拆成质数的积

算术基本定理：每个大于 1 的整数都可以唯一地分解成若干个质数的乘积（不考虑顺序）。

例如：60 = 2² × 3 × 5，100 = 2² × 5²。

分解方法——和判断质数类似，从小到大试除：

cpp

void factorize(int n) {
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {   // 能除尽就一直除
            cout << i << " ";   // i 是一个质因子
            n /= i;
        }
    }
    if (n > 1) cout << n;  // 最后剩下的也是质因子（如果有）
}
// 输入 60 → 输出：2 2 3 5

为什么这样分解出的因子一定是质数？因为合数因子（如 4）早有它的质因子（2）先被除干净了——轮到 4 的时候 n 已经不被 4 整除。

54.4 枚举约数："成对出现"的巧劲

n 的约数是成对出现的：如果 d 是 n 的约数，那么 n/d 也是。这对搭档中，较小的那个 ≤ √n。

因此枚举 n 的所有约数也只需要 O(√n)：

cpp

void printDivisors(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            cout << i << " ";           // 较小的约数
            if (i != n / i) {           // 如果是完全平方数，不要重复
                cout << n / i << " ";   // 较大的约数
            }
        }
    }
}
// 输入 36 → 输出：1 36 2 18 3 12 4 9 6

如果要按从小到大输出，可以先收集再排序：

cpp

vector<int> getDivisors(int n) {
    vector<int> divs;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) divs.push_back(n / i);
        }
    }
    sort(divs.begin(), divs.end());
    return divs;
}
// 输入 12 → 输出 {1, 2, 3, 4, 6, 12}

54.5 模运算：`%` 的数学性质

取模运算符 % 你早就认识了。现在来看它的数学性质——它们是数论的"基础语言"。

模运算三大性质：

（1）加法保留模：(a + b) % m = ((a % m) + (b % m)) % m

（2）乘法保留模：(a × b) % m = ((a % m) × (b % m)) % m

（3）减法保留模：(a - b) % m = ((a % m) - (b % m) + m) % m（注意 +m 处理负数结果）

cpp

// 实际应用：计算 (a × b) % mod，防止中间结果溢出
int mod_mul(int a, int b, int mod) {
    return ((long long)a * b) % mod;  // 先强转 long long 防溢出
}

// 计算 (a + b + c) % mod
int mod_add(int a, int b, int c, int mod) {
    return ((a % mod + b % mod) % mod + c % mod) % mod;
}

在竞赛中，你经常看到 #define MOD 1000000007 这种写法。为什么？因为大数相乘会爆 int，取模之后让结果始终在可控范围内。这就是模运算的威力——保持正确性的同时控制数值范围。

54.6 同余：两个数除以 m 余数相同

如果 a 和 b 除以 m 的余数相同，就说 a 与 b 模 m 同余，记作：

a ≡ b (mod m)

例如：17 ≡ 5 (mod 12)，因为 17 ÷ 12 和 5 ÷ 12 的余数都是 5。

同余的基本性质：

如果 a ≡ b (mod m)，c ≡ d (mod m)，则 a+c ≡ b+d (mod m)
如果 a ≡ b (mod m)，c ≡ d (mod m)，则 a×c ≡ b×d (mod m)

这些性质在做题中极为常用——做完加法和乘法后取模，不影响最终结果的模值。

54.7 数论小技巧速查

（1）快速判断闰年

cpp

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

（2）判断一个数是否是 3 的倍数

数位和能被 3 整除 → 原数能被 3 整除。例如 123 → 1+2+3=6，6%3==0 → 123 能被 3 整除。

cpp

bool divisibleBy3(int n) {
    int sum = 0;
    while (n > 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum % 3 == 0;
}

（3）欧拉筛思想（提前预告）

判断质数每次都试除到 √n 有点浪费——如果要判断很多个数，更好的方法是筛法——先做一个表格，把合数全部划掉，剩下的就是质数。这会在后续模块（下册）的算法章节详细介绍。现阶段理解"试除法到 √n"即可。

✋ 动手试试

试试 1：写一个程序，输入一个整数 n，输出 "是质数" 或 "不是质数"。测试 n=97（是）、n=100（不是）、n=1（不是）。

试试 2：输入一个整数 n，输出它的质因数分解结果。例如输入 84，输出 "84 = 2 * 2 * 3 * 7"。

试试 3：输入 n，输出 n 的所有约数，从小到大排列。看看 n=36 和 n=37 的约数数量差别有多大——这体现了质数的"稀有"。

试试 4：不用运算符 %，只用加减法，判断一个正整数 n 是否能被 3 整除。（提示：不断 -3，看最后能不能到 0。）

⚠️ 容易犯的错

错 1：忘记 1 不是质数

❌ isPrime(1) 返回 true

✅ if (n <= 1) return false; 必须显式排除

错 2：试除范围写成 i < n

❌ for (int i = 2; i < n; i++) → O(n)，太慢

✅ for (int i = 2; i * i <= n; i++) → O(√n)

错 3：质因数分解后忘记"剩下的因子"

❌ for (int i = 2; i*i <= n; i++) { while (n%i==0) { cout << i; n/=i; } } 到此为止

✅ if (n > 1) cout << n; 最后剩下的那个大于 √n 的质因子也要输出

错 4：负数取模结果不确定

❌ -7 % 3 在 C++ 中结果是 -1（而数学上我们常期望得到 2）

✅ 处理负数取模时，用 (a % m + m) % m 确保结果非负

📝 练习

基础题

1. 填空题

（1）如果 a % b == 0，则称 b ____ a，或者说 a 是 b 的 ____。

（2）大于 1 且只有 1 和自身两个约数的正整数叫 ____。

（3）判断一个数 n 是否为质数，试除法只需要试到 ____。

（4）(a + b) % m 等价于 ____。

（5）如果 a 和 b 除以 m 的余数相同，则称 a 与 b 模 m ____，记作 a ≡ b (mod m)。

2. 简答题

"任何一个合数 n 必定有一个不超过 √n 的质因子"——这句话为什么成立？请用反证法或乘积关系简要说明。

提高题

3. 编程题 — 区间质数

输入 L 和 R（1 ≤ L ≤ R ≤ 10⁶），输出 [L, R] 内的所有质数。

（提示：对区间内每个数用试除法？可以，但 O((R-L)×√R) 可能接近 10⁹。想想有没有更聪明的方法——用筛法，在 R 的范围内一次性把所有质数找出来。可以先实现简单版（每个数单独判断），把区间设小一点测试。）

4. 编程题 — 约数个数

输入 n，输出 n 的约数个数。例如 n=12 有 6 个约数（1,2,3,4,6,12）。

（提示：不需要真列出所有约数。如果 n = p₁^a₁ × p₂^a₂ × …，则约数个数 = (a₁+1)×(a₂+1)×…。先做质因数分解，再套公式。）

挑战题

5. 编程题 — 质数距离

输入一个偶数 n（n ≥ 4），输出两个质数 p 和 q 使得 p + q = n（哥德巴赫猜想的验证题）。如果有多个解，输出 p 最小的那一组。

输入：20
输出：3 17 （因为 3+17=20，且 3 是最小的可能 p）

6. 编程题 — 模意义下的快速幂

计算 a^b mod m。a、b、m 的值最大可达 2×10⁹。

（提示：不能先算 a^b 再取模——a^b 可能是一个天文数字。用"快速幂"思想：a^b = (a^(b/2))² 如果 b 是偶数；a^b = a × (a^(b/2))² 如果 b 是奇数。每一步都取模，控制在 mod 范围内。这就是"模意义下的快速幂"，下一篇模块会详讲。）

🧠 本章小结

整除：a % b == 0 → b | a

质数：大于 1 且只被 1 和自身整除
    判断：试除到 √n → O(√n)

质因数分解：从小到大试除，能除尽就一直除
    for i=2 to √n: while n%i==0: 输出i, n/=i
    最后 if n>1: 输出 n

约数枚举：成对出现，只枚举到 √n
    对每个 i: 若 n%i==0, 输出 i 和 n/i（注意去重）

模运算：
    (a+b)%m = ((a%m)+(b%m))%m
    (a×b)%m = ((a%m)×(b%m))%m
    (a-b)%m = ((a%m)-(b%m)+m)%m

同余：a ≡ b (mod m) ← 除以 m 的余数相同

📝 配套练习

共7题。质数判定→分解→筛法→约数→模运算，初等数论核心链全覆盖。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P5736	https://hydro.ac/p/luogu-P5736	质数判定、O(√n)
◆ 拓展	luogu-P1075	https://hydro.ac/p/luogu-P1075	质因数分解、O(√n)
◆ 拓展	luogu-P5723	https://hydro.ac/p/luogu-P5723	质数口袋、筛法思想
◆ 拓展	luogu-P1217	https://hydro.ac/p/luogu-P1217	回文质数、双重判定
◆ 拓展	luogu-P5738	https://hydro.ac/p/luogu-P5738	约数枚举、歌唱比赛变体
◆ 拓展	luogu-P5746	https://hydro.ac/p/luogu-P5746	模运算、同余
◆ 拓展	luogu-P5748	https://hydro.ac/p/luogu-P5748	约数、完全数

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 6 道◆拓展题，覆盖不同变式和细节。

配套练习

共7题。质数判定→分解→筛法→约数→模运算，初等数论核心链全覆盖。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P5736	https://hydro.ac/p/luogu-P5736	质数判定、O(√n)
◆ 拓展	luogu-P1075	https://hydro.ac/p/luogu-P1075	质因数分解、O(√n)
◆ 拓展	luogu-P5723	https://hydro.ac/p/luogu-P5723	质数口袋、筛法思想
◆ 拓展	luogu-P1217	https://hydro.ac/p/luogu-P1217	回文质数、双重判定
◆ 拓展	luogu-P5738	https://hydro.ac/p/luogu-P5738	约数枚举、歌唱比赛变体
◆ 拓展	luogu-P5746	https://hydro.ac/p/luogu-P5746	模运算、同余
◆ 拓展	luogu-P5748	https://hydro.ac/p/luogu-P5748	约数、完全数

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 6 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我能判断一个数是否为质数（O(√n)）
[ ] 我能写出质因数分解的代码
[ ] 我知道为什么试除只到 √n 就够了
[ ] 我能用"成对出现"的方法枚举一个数的所有约数
[ ] 我理解模运算的加法、乘法保留性质
[ ] 我能解释同余的简单含义
[ ] 我知道怎样快速判断闰年

🚀 下章预告

有了整除、质数的概念，接下来一个自然的问题是：两个数之间有什么共同的"血缘关系"？比如 12 和 18——它们都能被 6 整除，6 就是它们的最大公约数；它们都能被 3 整除，3 呢？没有 6 大。那怎么高效求两个数的最大公约数？最小公倍数呢？下一章带你走进辗转相除的优雅世界。

第 54 章 数字的奥秘——初等数论 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

54.1 整除与约数 ​

54.2 质数：只能被 1 和自身整除的数 ​

试除法判断质数：O(√n) ​

54.3 质因数分解：把合数拆成质数的积 ​

54.4 枚举约数："成对出现"的巧劲 ​

54.5 模运算：% 的数学性质 ​

54.6 同余：两个数除以 m 余数相同 ​

54.7 数论小技巧速查 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：忘记 1 不是质数 ​

错 2：试除范围写成 i < n ​

错 3：质因数分解后忘记"剩下的因子" ​

错 4：负数取模结果不确定 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​

🚀 下章预告 ​