数论¶

方法速览¶

任务	方法	口诀
判质数	试除到 \(\sqrt{n}\)	除到根号停
1 和 2	1 不是质数也不是合数；2 是唯一偶质数	一非质，二独偶
因子	\(i\) 与 \(n/i\) 成对出现	因子成双
筛法	埃氏筛每合数被划多次 \(O(n\log\log n)\)；欧拉筛只被最小质因子划一次 \(O(n)\)	埃氏重复划，欧拉一遍过
GCD	辗转相除 \(\gcd(a,b) = \gcd(b, a \bmod b)\)	大数模小数
LCM	\(\dfrac{a}{\gcd(a,b)} \times b\)（先除后乘）	先除后乘防溢出

质数与试除判质数¶

质数（素数）：大于 1 的自然数中，因子只有 1 和自身。

\(0\)、\(1\) 不是质数（1 连质数带合数都不算）；
\(2\) 是唯一的偶质数——也是最小的质数；
常考易错：\(91 = 7\times13\)（不是质数）、\(87 = 3\times29\)、\(57 = 3\times19\)；100 以内最大质数是 97。

试除法：若 n 有大于 \(\sqrt{n}\) 的因子，必配一个小于 \(\sqrt{n}\) 的——只需试到 \(\sqrt{n}\)：

bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; (long long)i * i <= n; i++)
        if (n % i == 0) return false;
    return true;
}

注意用 i * i <= n 而不是 i <= sqrt(n)（浮点误差），且 i*i 要防 int 溢出。

因子与质因子¶

因子成对：枚举 \(i \le \sqrt{n}\)，一次收获 \(i\) 和 \(n/i\)（相等时只算一次）；
因子个数奇偶：只有完全平方数的因子个数是奇数（有一对 \(i = n/i\) 重合）；
质因子分解：从小到大除尽再前进——for (i = 2; i*i <= n; ) if (n%i==0) n/=i; else i++;

例：36 的因子 = \(\{1,2,3,4,6,9,12,18,36\}\) 共 9 个（奇数个，因为 36 是完全平方数）；\(360 = 2^3\times3^2\times5\)，因子个数 \(= (3+1)(2+1)(1+1) = 24\) 个。

埃氏筛与欧拉筛¶

埃氏筛：每个质数 p 划掉它的倍数：

for (int i = 2; i <= n; i++)
    if (!vis[i]) {
        prime[++cnt] = i;
        for (int j = i + i; j <= n; j += i) vis[j] = true;
    }

复杂度 \(O(n\log\log n)\)：一个合数会被它的每个质因子各划一次（如 12 被 2、3 各划）。

欧拉筛（线性筛）：只让每个合数被其最小质因子划掉一次：

for (int i = 2; i <= n; i++) {
    if (!vis[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt && (long long)i * prime[j] <= n; j++) {
        vis[i * prime[j]] = true;
        if (i % prime[j] == 0) break;   // prime[j] 已是 i 的因子 → 保证最小质因子
    }
}

复杂度 \(O(n)\)——break 那行是灵魂。

GCD 与 LCM¶

辗转相除（欧几里得）：\(\gcd(a, b) = \gcd(b, a \bmod b)\)，直到余数为 0：

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }   // 先除后乘防溢出

例（2019 真题）：\(\gcd(319, 377)\) 逐步：

步	大数	小数	余
1	377	319	58
2	319	58	29
3	58	29	0 → 答案 29

LCM：\(\text{lcm}(319, 377) = \dfrac{319}{29}\times377 = 11\times377 = 4147\)。

互质：\(\gcd(a,b)=1\)；同余：\(a \equiv b \pmod m\)，加减乘都保序（除法不行）。

练习题目¶

练习 1 · 质数的定义¶

题目

下列说法正确的是（）

A. 1 是最小的质数
B. 2 是唯一的偶质数
C. 0 是质数
D. 所有奇数都是质数

答案与解析

答案：B

质数要“大于 1 且因子只有 1 和自身”；1 不达标（A/C 错）；9、15 都是奇数但不是质数（D 错）。

练习 2 · 易错合数¶

题目

下列数中是质数的是（）

A. \(91\)
B. \(87\)
C. \(89\)
D. \(57\)

答案与解析

答案：C

\(91 = 7\times13\)、\(87 = 3\times29\)、\(57 = 3\times19\) 都是“看着像质数的合数”——大数先试 2、3、5、7。

练习 3 · 100 内最大质数¶

题目

100 以内最大的质数是（）

A. \(97\)
B. \(99\)
C. \(98\)
D. \(93\)

答案与解析

答案：A

\(99 = 9\times11\)、\(98 = 2\times49\)、\(93 = 3\times31\)；97 无法分解——记住 97。

练习 4 · 试除上界¶

题目

判断 101 是否为质数，最多要试除到（）

A. \(50\)
B. \(100\)
C. \(101\)
D. \(10\)

答案与解析

答案：D

\(\sqrt{101} \approx 10.05\)，试 2~10 即可（都不整除 → 质数）。因子成对，过 \(\sqrt{n}\) 无新信息。

练习 5 · 为什么到根号¶

题目

试除判质数只需到 \(\sqrt{n}\)，原因是（）

A. 大于 \(\sqrt{n}\) 的数不用考虑
B. 若 n 有大于 \(\sqrt{n}\) 的因子 d，则 \(n/d < \sqrt{n}\) 必先被试到
C. \(\sqrt{n}\) 之后是合数
D. 计算机限制

答案与解析

答案：B

因子成对：\(d \times (n/d) = n\)，一边超根号另一边必低于根号——小边全试过没中，大边就不存在。

练习 6 · 因子个数¶

题目

24 的因子个数是（）

A. \(6\)
B. \(4\)
C. \(10\)
D. \(8\)

答案与解析

答案：D

\(24 = 2^3\times3\)，因子个数 \((3+1)(1+1) = 8\)：\(\{1,2,3,4,6,8,12,24\}\)。

练习 7 · 因子成对枚举¶

题目

枚举 n 的因子用 \(i \le \sqrt{n}\) 循环，每次命中 i 同时收获（）

A. 只有 i
B. \(n - i\)
C. i 和 \(i+1\)
D. i 和 \(n/i\)

答案与解析

答案：D

\(i\) 整除 n 则 \(n/i\) 也是因子——一对一次拿，循环量降到 \(\sqrt{n}\)。

练习 8 · 奇数个因子¶

题目

因子个数为奇数的数是（）

A. 完全平方数
B. 质数
C. 偶数
D. 3 的倍数

答案与解析

答案：A

只有平方数有一对重合的 \(i = n/i\)，配对数加一成奇——如 36 有 9 个因子。

练习 9 · 质因子分解¶

题目

\(360\) 的质因子分解是（）

A. \(2^3 \times 3^2 \times 5\)
B. \(2^2 \times 3^2 \times 10\)
C. \(2^3 \times 3 \times 15\)
D. \(8 \times 9 \times 5\)

答案与解析

答案：A

质因子分解必须拆到全是质数：10、15、8 都还是合数（B/C/D 违规）。

练习 10 · 埃氏筛的动作¶

题目

埃氏筛遇到质数 3 时会划掉（）

A. 只有 9
B. 所有奇数
C. 6、9、12、15、…（3 的所有倍数）
D. 3 和 5

答案与解析

答案：C

质数 p 的任务就是划掉 \(2p, 3p, 4p\dots\)；6 已被 2 划过但照划不误——这正是埃氏筛重复劳动的来源。

练习 11 · 埃氏筛的重复¶

题目

合数 60 在埃氏筛中被划掉（）次。

A. \(1\)
B. \(3\)（被 2、3、5 各一次）
C. \(12\)
D. \(0\)

答案与解析

答案：B

60 的不同质因子是 2、3、5，各划一次——合数的质因子越多被划越多次。

练习 12 · 欧拉筛的关键行¶

题目

欧拉筛（线性筛）中 if (i % prime[j] == 0) break; 的作用是（）

A. 提前退出省一点时间
B. 保证每个合数只被其最小质因子划掉一次，达成 O(n)
C. 防止数组越界
D. 判断 i 是不是质数

答案与解析

答案：B

prime[j] 整除 i 时，更大的 prime[j'] 乘 i 的最小质因子其实是 prime[j]——再划就重复；break 保住“一合一划”。

练习 13 · 两种筛的复杂度¶

题目

埃氏筛与欧拉筛的时间复杂度分别是（）

A. \(O(n)\) 和 \(O(n\log n)\)
B. 都是 \(O(n\log n)\)
C. 都是 \(O(n)\)
D. \(O(n\log\log n)\) 和 \(O(n)\)

答案与解析

答案：D

\(\log\log n\) 增长极慢，实战两者都够用；数据量到 \(10^8\) 级才显出线性筛优势。

练习 14 · 辗转相除第一步¶

题目

\(\gcd(48, 18)\) 的第一步是（）

A. \(48 - 18 = 30\)
B. \(\gcd(48, 18 \times 2)\)
C. \(\gcd(18, 48 \bmod 18) = \gcd(18, 12)\)
D. \(48 / 18 = 2.67\)

答案与解析

答案：C

辗转相除把“大数，小数”换成“小数，余数”：\(48 = 2\times18 + 12\) → \(\gcd(18, 12)\)。

练习 15 · GCD 手算¶

题目

\(\gcd(48, 18)\) = （）

A. \(6\)
B. \(2\)
C. \(3\)
D. \(18\)

答案与解析

答案：A

\(\gcd(48,18)\to\gcd(18,12)\to\gcd(12,6)\to\gcd(6,0) = 6\)。

练习 16 · GCD 与 0¶

题目

\(\gcd(n, 0)\) = （）

A. \(0\)
B. 未定义
C. \(1\)
D. \(n\)

答案与解析

答案：D

任何数整除 0，最大公约数取另一个数——这也是辗转相除的递归终点。

练习 17 · LCM 公式¶

题目

\(\text{lcm}(12, 18)\) = （）

A. \(216\)
B. \(72\)
C. \(36\)
D. \(6\)

答案与解析

答案：C

\(\gcd = 6\)，\(\text{lcm} = \dfrac{12}{6}\times18 = 36\)。A 是 \(12\times18\)（没除 gcd）。

练习 18 · 先除后乘¶

题目

lcm 写成 a * b / gcd(a, b) 的问题与正解是（）

A. 没问题
B. a * b 可能溢出；应写 a / gcd(a, b) * b
C. 结果错；应写 a + b
D. 只对质数有效

答案与解析

答案：B

两个接近 int 上限的数先乘必爆；先除后乘把中间量压回 a 的量级。

练习 19 · 互质¶

题目

下列与 8 互质的数是（）

A. \(12\)
B. \(20\)
C. \(16\)
D. \(9\)

答案与解析

答案：D

互质 = 公因数只有 1：\(\gcd(8,9) = 1\)；12、16、20 都含因子 2。

练习 20 · 同余的可乘性¶

题目

已知 \(a \equiv b \pmod m\)，则一定有（）

A. \(2a \equiv 2b \pmod m\)
B. \(a/2 \equiv b/2 \pmod m\)
C. \(a^2 \equiv b \pmod m\)
D. \(a \equiv 2b \pmod m\)

答案与解析

答案：A

同余对加、减、乘封闭；除法不保（\(4 \equiv 1 \pmod 3\) 但 \(2 \not\equiv 0.5\)）。

练习 21 · 判质的最快小排除¶

题目

快速排除 5823 是质数，只需注意到（）

A. 它是奇数
B. 各位数字和 \(5+8+2+3 = 18\) 是 9 的倍数 → 被 3 整除
C. 末位不是 5
D. 它大于 100

答案与解析

答案：B

数字和被 3（9）整除则原数被 3（9）整除——试 2、5 看末位，试 3、9 看数位和，四关过了再试除。

练习 22 · 质数分布¶

题目

20 以内的质数共有（）个。

A. \(8\)
B. \(7\)
C. \(10\)
D. \(9\)

答案与解析

答案：A

\(2,3,5,7,11,13,17,19\) 共 8 个——2 别漏（唯一的偶数）。

练习 23 · 唯一分解¶

题目

任意大于 1 的自然数（）

A. 都能唯一分解成质数的乘积（不计顺序）
B. 都能唯一分解成奇数的乘积
C. 只有偶数能分解
D. 分解方式有无穷多种

答案与解析

答案：A

算术基本定理：质因子分解唯一——它是因子个数公式 \((e_1+1)(e_2+1)\cdots\) 的根基。

练习 24 · GCD 的性质¶

题目

\(\gcd(ka, kb)\) = （）（k 为正整数）

A. \(k + \gcd(a,b)\)
B. \(\gcd(a, b)\)
C. \(k \cdot \gcd(a, b)\)
D. \(k^2\gcd(a,b)\)

答案与解析

答案：C

公因子整体放大 k 倍；相对地 \(\text{lcm}(ka,kb) = k\cdot\text{lcm}(a,b)\)。

练习 25 · 连续数互质¶

题目

相邻两个自然数 n 与 n+1（）

A. 一定互质
B. 一定不互质
C. 仅 n 为偶数时互质
D. 无法确定

答案与解析

答案：A

若有公因子 d > 1 整除两数，则整除差 \(1\)——矛盾。所以 \(\gcd(n, n+1) = 1\)。

练习 26 · 综合判断¶

题目

下列说法错误的是（）

A. 1 既不是质数也不是合数
B. 完全平方数的因子个数是奇数
C. 两个质数的乘积一定是质数
D. 埃氏筛的复杂度是 \(O(n\log\log n)\)

答案与解析

答案：C

质数相乘得到合数（至少有这两个质因子）。

历年真题¶

2019 年 · 第 9 题¶

题目

\(100\) 以内最大的素数是（）。

A. \(89\)
B. \(93\)
C. \(91\)
D. \(97\)

答案与解析

答案：D

99、98 不是质数，从 97 往回验：97 不能被 \(2\sim10\)（\(\sqrt{97} < 10\)）整除 → 质数。C 的 \(91 = 7\times13\) 是著名陷阱。

2019 年 · 第 10 题¶

题目

\(319\) 和 \(377\) 的最大公约数是（）。

A. \(29\)
B. \(33\)
C. \(31\)
D. \(27\)

答案与解析

答案：A

辗转相除：\(377 = 1\times319 + 58\)；\(319 = 5\times58 + 29\)；\(58 = 2\times29 + 0\) → \(\gcd = 29\)（三步出答案）。

易错小结¶

1 不是质数；2 是唯一偶质数；易错合数：91、87、57；100 内最大质数 97；
试除只到 \(\sqrt{n}\)（因子成对）；判整除先过四关：⅖ 看末位、3/9 看数位和；
因子个数：质因数分解 \((e_1+1)(e_2+1)\cdots\)；平方数因子个数才是奇数；
埃氏筛 \(O(n\log\log n)\)（合数被每个质因子划）；欧拉筛 \(O(n)\)（只被最小质因子划，i % prime[j] == 0 即 break）；
\(\gcd(a,b) = \gcd(b, a\bmod b)\)、\(\gcd(n,0) = n\)；lcm 先除后乘防溢出；
同余可加减乘、不可除；相邻自然数必互质。