🔢 初等数论

数论是研究整数的学问，整数的世界像一堆积木：有的积木再也拆不动，有的能拆成小块，还有「最大公约数」「最小公倍数」这样的好朋友关系。这一页我们把整数玩明白，还会学超快的「筛子」把质数一个个找出来。

考纲知识点：素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性
欧几里得算法
唯一分解定理
素数表的埃氏筛法和线性筛法

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级

(1)掌握初等数论相关知识的概念和应用，包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。
(4)掌握辗转相除法（也称欧几里得算法）、素数表的埃氏筛法和线性筛法、唯一分解定理的原理和应用。

说明：C++ 五级「初等数论」在官网详述中对应 (1) 与 (4) 两条，其中 (4) 对应知识点表里的「欧几里得算法 / 唯一分解定理 / 素数表的埃氏筛法和线性筛法」三行，本页两条并列呈现。

📚

先学一学

花 5 分钟读完下面 5 课，再去闯关就不慌啦

🧱 质数与合数、约数与倍数

整数像积木。质数（素数）是再也拆不动的小积木：只能写成 1 × 自己，比如 2、3、5、7。合数还能继续拆，比如 4 = 2 × 2、6 = 2 × 3。特别记住：1 既不是质数也不是合数。

🆚 约数 vs 倍数：一对相反的关系

若 a × b = c，就说 a、b 都是 c 的约数（因数），c 是 a、b 的倍数。判断用取余：24 % 6 == 0，所以 6 是 24 的约数、24 是 6 的倍数。
12 的约数：1、2、3、4、6、12；12 的倍数：12、24、36……

💡 口诀：质数拆不动，合数还能拆；1 是「光杆司令」两边都不算。约数是「分得开它」，倍数是「它分得开别人」。

🌟 小发现

2 是唯一一个又是偶数又是质数的数——其他偶数都能被 2 拆开呀。找质数时先看奇偶能快一半。

🪢 最大公约数 & 最小公倍数：剪绳子与铺瓷砖

有两根绳子，一根 12 米、一根 18 米，要剪成同样长的小段且刚好剪完，每段最长几米？答案就是 12 和 18 的最大公约数（gcd）：6 米（12÷6=2 段，18÷6=3 段）。

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

数很大时别一个个试约数，用「大数除以小数取余数，再用除数除余数」，一直除到余数为 0，最后一个除数就是最大公约数。算 gcd(18, 12)：
18 ÷ 12 余 6 → 12 ÷ 6 余 0 → gcd = 6。

看得懂就好，不用背：

int gcd(int a, int b){
  while (b != 0){
    int t = a % b;
    a = b;
    b = t;
  }
  return a;
}

💡 口诀：大除小、取余数；除数再除余数；余零停，除数就是 gcd。

🔁 最小公倍数（lcm）

铺瓷砖要让两种尺寸都刚好对齐，需要最小公倍数。它有个好公式：lcm(a, b) = a × b ÷ gcd(a, b)。所以 lcm(12, 18) = 12×18÷6 = 36。

💡 口诀：gcd 管「剪绳子最长的公共段」，lcm 管「对齐的最短公共倍」；先求 gcd，再乘除就得到 lcm。

🕐 同余与模运算：钟表和星期都会转圈

取余（模运算）是算「除完剩多少」：17 % 5 = 2（17 除以 5 余 2）。钟表每 12 小时转一圈，13 点其实就是 13 % 12 = 1 点。星期几就是「对 7 取余」的循环。

🤝 同余：余数一样就是「同余」

14 点和 26 点，对 12 取余都余 2，钟面上都指向 2 点，就说它们在模 12 下同余。程序里经常用取余判断循环的位置，比如一列表格每行放 4 个，第几个就落在第几列。

💡 口诀：模运算是「除完看剩余」；同余是「余数相同、转在同一格」。

⚖️ 奇偶性：对 2 取余

偶数 % 2 == 0，奇数 % 2 == 1。奇偶也是「模 2 同余」：两个偶数或两个奇数关于 2 同余。奇偶相加有规律：奇 + 奇 = 偶、偶 + 偶 = 偶、奇 + 偶 = 奇。

看得懂就好，不用背：

if (x % 2 == 0) cout << "偶数";
else cout << "奇数";

💡 口诀：奇奇相加变偶、偶偶相加还偶、一奇一偶变奇；对 2 取余一眼看清。

🧩 质因数分解：把合数拆成「质数积木」

把合数拆成一串质数相乘就是质因数分解，像把大城堡拆回一块块标准积木：60 = 2 × 2 × 3 × 5。用「短除法」：先用最小质数 2 试除，除不动换 3、再换 5……一路除到商是质数为止。

🪪 唯一分解定理：每个数的「指纹」只有一种

只要不管乘的顺序，任何一个大于 1 的整数，拆成质数乘积的方式是唯一的。60 只能拆成 2×2×3×5，绝不会有第二套拆法（2×3×10 里 10 还能再拆，不算到底）。这就是唯一分解定理。

💡 口诀：拆到底、全是质数才算完；不管顺序只有一种，像指纹一样唯一。

🌟 行业实际：大数难分解保护了密码

把一个很大的数（几百位）拆回质因数特别难，现代网络加密正是利用「分解难」来保护你的密码和支付信息。工程师也常借唯一分解来判断两个数是否「互质」、约分是否到底。

🥅 埃氏筛：划掉倍数，筛出质数表

要一次性找出 1~n 里所有质数，别每个都单独试除，用筛子：先写 2~n，从 2 开始，把它的倍数统统划掉；下一个没被划掉的是质数，再划掉它的倍数……最后没被划掉的全是质数。就像用漏勺筛豆子，把「合数」都漏掉。

🥅 埃氏筛演示（找 20 以内质数）

划掉 2 的倍数：4、6、8、10、12、14、16、18、20 ✗
下一个 3 是质数，划掉 9、15 ✗
下一个 5 是质数，划掉 25 已超 20 不用管……
剩下没被划掉的：2、3、5、7、11、13、17、19，全是质数！

💡 口诀：从 2 开始，留下质数、划掉它所有倍数；划到根号 n 就够，剩下的都是宝。

💻 读代码：埃氏筛的骨架

看得懂就好，不用背：

bool notPrime[1000] = {};
for (int i = 2; i * i <= n; i++){
  if (!notPrime[i])
    for (int j = i * i; j <= n; j += i)
      notPrime[j] = true;
}

从 i * i 开始划，因为更小的倍数早被划过了；notPrime[j] = true 表示 j 是合数。

💡 口诀：埃氏筛「留质划倍」；每个合数可能被划几次。

🆚 埃氏筛 vs 线性筛

· 埃氏筛：好懂好写，但同一个合数可能被不同的质数划掉多次。
· 线性筛：让每个合数只被它的最小质因数划掉一次，更快更「线性」，所以叫线性筛。
· 单个数字问「是不是质数」用试除；要一批质数表用筛子。

💡 口诀：问单个用试除，求整表用筛子；埃氏简单会重复，线性每数划一次。

🎯

闯关小锦囊 · 考点提醒

质数只能拆成 1×自己；合数还能再拆；1 两边都不算；2 是唯一的偶质数。
约数是「分得开它」的因数，倍数是它自己不断翻倍；用 % == 0 判断。
最大公约数 gcd：欧几里得算法（辗转相除）大除小取余，除到 0 为止；最小公倍数 lcm = a×b÷gcd。
同余：除以同一模数余数相同（钟表 12、星期 7）；奇偶就是对 2 取余，奇奇为偶、偶偶为偶、一奇一偶为奇。
质因数分解拆到底全是质数；唯一分解定理：不计顺序，拆法只有一种。
要一批质数表用埃氏筛（留质划倍）或线性筛（每个合数只划一次）。
筛法复杂度：线性筛 O(n) 比 埃氏筛 O(n log log n) 更快；埃氏筛会重复划同一个合数。

🎮

学完了？来闯关！

下面 16 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。