【GESP】C++五级考试大纲知识点梳理, (1) 初等数论
GESP C++五级官方考试大纲中，共有9条考点，本文针对第1条考点进行分析介绍。
（1）掌握初等数论相关知识的概念和应用，包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。
由于本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。
数论是研究整数（也就是我们常说的“整个数”）的数学分支。初等数论是数论的基础部分，里面有一些简单但很有意思的概念，帮助我们了解数字的“秘密”。
一、素数与合数
1.1 定义
- 素数（质数）：大于1的自然数，如果它只有1和它本身两个因数（只能被1和自己整除），就叫素数。比如：2、3、5、7、11。
- 合数：大于1的自然数，如果它不是素数（也就是说，除了1和它本身，还有其他因数），就叫合数。比如：4（能被2整除）、6（能被2和3整除）、9（能被3整除）。
1.2 说明
- 素数就像数的“基本零件”，因为任何大于1的数都可以用素数乘起来表示。
- 合数则可以“拆开”成更小的数相乘。
二、最大公约数（GCD）与最小公倍数（LCM）
2.1 定义
- 最大公约数（GCD）：两个或多个数的公约数（能同时整除它们的数）中最大的那个。比如，8和12的公约数有1、2、4，最大的是4，所以$\mathrm{GCD}(8, 12) = 4$。
- 最小公倍数（LCM）：两个或多个数的公倍数（它们都能整除的数）中最小的一个。比如，8和12的公倍数有24、48、72，最小的是24，所以$\mathrm{LCM}(8, 12) = 24$。
2.2 计算方法
重点介绍 最大公约数（GCD） 和 最小公倍数（LCM） 的公式和解释
2.2.1 求最大公约数（Greatest Common Divisor, GCD）
求法一：列出所有约数
适合小数：
- 12 的约数：1, 2, 3, 4, 6, 12
- 18 的约数：1, 2, 3, 6, 9, 18 → 最大的公共约数是 6
求法二：辗转相除法（欧几里得算法）
适合大一点的数，步骤如下：
- 用大数 $\div$ 小数，求余数
- 用原来的小数和余数再进行除法
- 一直除下去，直到余数是0
- 最后那个不为0的数，就是最大公约数！
例如：
\[\text{GCD}(48, 18)\]步骤：
- $48 \div 18 = 2$ 余 $12$
- $18 \div 12 = 1$ 余 $6$
- $12 \div 6 = 2$ 余 $0$ → 所以 GCD = 6
2.2.2 求最小公倍数（Least Common Multiple, LCM）
最重要的公式：
对于任意两个正整数 a 和 b：
\[\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}\]例如：
求 12 和 18 的最小公倍数：
我们已经知道：
- 12 × 18 = 216
- GCD(12, 18) = 6
所以：
\[\text{LCM}(12, 18) = \frac{12 \times 18}{6} = \frac{216}{6} = 36\]
注：最大公约数和最小公倍数的关系
GCD × LCM = 两个数的乘积 \(\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b\)
例如：
对于数 $12$ 和 $18$：
- $\text{GCD}(12,18) = 6$
- $\text{LCM}(12,18) = 36$
- $6 \times 36 = 216 = 12 \times 18$
2.3 典型应用场景
- GCD可以用来简化分数，比如$\frac{8}{12}$可以约分成$\frac{2}{3}$。
- LCM能帮我们解决“对齐”问题，比如两个人分别每3天和每4天跑步一次，他们下次一起跑步是第几天？答案是$\mathrm{LCM}(3, 4) = 12$天。
三、同余与模运算
3.1 定义
模运算：一个数除以另一个数后取余数。比如，$17 \div 5 = 3$余2，所以$17 \mod 5 = 2$。
同余：如果两个数$a$和$b$除以同一个数$m$余数相同，就说$a$和$b$模$m$同余，写成: \(a \equiv b \pmod{m}\)
例如，$17 \equiv 7 \pmod{5}$。
3.2 说明
- 同余就像”钟表数学”。比如，钟表是12小时一循环，13点其实就是1点，因为 $13 \equiv 1 \pmod{12}$。
- 在生活中，它可以用来算星期几，或者在计算机里做循环计算。
四、约数与倍数
4.1 定义
- 约数：如果一个数 $d$ 能整除另一个数 $n$（除完没余数），$d$ 就是 $n$ 的约数。比如，$12$ 的约数有 $1$、$2$、$3$、$4$、$6$、$12$。
- 倍数：如果一个数 $m$ 能被另一个数 $n$ 整除，$m$ 就是 $n$ 的倍数。比如，$12$ 是 $3$ 的倍数，因为 $12 \div 3 = 4$。
4.2 说明
- 约数告诉我们一个数能被哪些数整除，倍数告诉我们一个数能整除哪些数。
- 比如，12的约数是1、2、3、4、6、12，它的倍数有12、24、36……
4.3 常用公式
约数个数公式
- 如果一个数的质因数分解是 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，它的约数个数是 $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$。
- 例子：12 = $2^2 \times 3^1$，约数个数 = $(2 + 1)(1 + 1) = 3 \times 2 = 6$（约数是1、2、3、4、6、12）。
五、质因数分解
5.1 定义
- 把一个大于1的自然数，用素数（质数）相乘的形式表示出来，这个过程就叫做质因数分解。
- 比如，$12$ 可以写成 $2 \times 2 \times 3$。
为什么要学质因数分解？
- 用来求最大公约数、最小公倍数
- 在分数约分中很常用
- 有助于理解数的结构和倍数关系
- 是初中代数和数学竞赛的基础工具
5.2 定理
- 算术基本定理：每个大于1的自然数都可以唯一地分解成素数相乘（顺序不算）。
5.3 常用分解方法
5.3.1 方法一：短除法（连除法） —— 常用
步骤如下：
- 从最小的素数 $2$ 开始除
- 能除尽就一直除；不能除就换下一个素数 $(3,5,7,\ldots)$
- 一直除到最后结果是 $1$ 为止
- 把所有除数写下来，它们就是质因数
例如：分解 60
| 除数（素数） | 被除数 | 商 |
|---|---|---|
| 2 | 60 | 30 |
| 2 | 30 | 15 |
| 3 | 15 | 5 |
| 5 | 5 | 1 |
所以：
\[60 = 2 \times 2 \times 3 \times 5 = 2^2 \times 3 \times 5\]5.3.2 方法二：分解因数树（因数分解图）
把一个数分解成两个数的乘积，然后继续把每个数再分解，直到每个数都是素数。结构像“树”。
例如：分解 36
1
2
3
4
5
36
/ \
6 6
/ \ / \
2 3 2 3
所以：
\[36 = 2 \times 2 \times 3 \times 3 = 2^2 \times 3^2\]判断是否已经分解完成的方法
- 如果每一个因数都是素数，就结束了。
- 常见素数有：2、3、5、7、11、13、17、19…
5.4 小技巧
- 如果一个数是偶数，一定可以先除以2。
- 如果个位数是5或0，可以除以5。
- 如果各位数字加起来是3的倍数，可以除以3。
六、奇偶性
6.1 定义
- 偶数：能被2整除的数，比如2、4、6、8。
- 奇数：不能被2整除的数，比如1、3、5、7。
6.2 说明
- 奇偶性的一般规律：
- $\text{奇数} + \text{奇数} = \text{偶数}$（比如$3 + 5 = 8$）
- $\text{偶数} + \text{偶数} = \text{偶数}$（比如$4 + 6 = 10$）
- $\text{奇数} + \text{偶数} = \text{奇数}$（比如$3 + 4 = 7$）
- $\text{奇数} \times \text{奇数} = \text{奇数}$（比如$3 \times 5 = 15$）
- $\text{偶数} \times \text{偶数} = \text{偶数}$（比如$4 \times 6 = 24$）
- $\text{奇数} \times \text{偶数} = \text{偶数}$（比如$3 \times 4 = 12$）
- 这些规律在数学证明中经常用到。
七、总结
素数和合数是最基本的分类，GCD和LCM帮我们处理分数和周期问题，同余让我们看到数的循环规律，约数和倍数揭示数的除法关系，质因数分解把数拆成“零件”，奇偶性则带来简单的加法、乘法规律。
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
GESP各级别考纲、真题讲解、知识拓展和练习清单等详见【置顶】【GESP】C++ 认证学习资源汇总
“luogu-”系列题目已加入洛谷Java、C++初学团队，作业清单，可在线评测，团队名额有限。
“bcqm-”系列题目可在编程启蒙题库进行在线评测。
欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答
欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总
欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助
