质数与合数 知识点讲解

概念

在信息学竞赛里，数论题往往像是一场“拆礼物”的游戏：给你一个巨大的数字，让你把它拆解成最基础的“积木”（质数）堆，或者反过来，给你一堆积木问能拼出多少种不同的礼物。而这一切的起点，就是质数与合数的概念。

想象一下，你手里有一堆不同大小的积木块。有些积木块非常“单纯”，它们身上只有两个“把手”（因数）：一个是数字 1，另一个就是它自己。比如数字 2，它的把手是 1 和 2；数字 3，把手是 1 和 3。这种只有两个把手的正整数，我们叫它质数。除了 1 和质数之外，其他的正整数都有超过两个把手，比如 4 有 1、2、4 三个把手，6 有 1、2、3、6 四个把手，这种我们就叫它合数。

这个概念看似简单，但它是数论题的起点：绝大多数数论题都在做一件事 —— 把一个数拆成质数的乘积（质因数分解）。

️ 一个必须记牢的边界：1 既不是质数，也不是合数。 这是最容易写错也最容易在客观题里被坑的一点。另外 2 是唯一的偶质数 —— 很多"两个质数的和/差"的题，答案都藏在"2 很特殊"这个点上。

触发清单（看到这些信号第一时间想到本知识点）

定义

① 判断质数：试除法，只需试到 √n

bool isPrime(long long n) {
 if (n < 2) return false; //  0 和 1 都不是质数
 for (long long i = 2; i * i <= n; i++) // 只试到 sqrt(n)
 if (n % i == 0) return false;
 return true;
}

为什么只试到 √n：如果 n = a × b 且 a ≤ b，那么 a ≤ √n。所以只要在 2..√n 里找不到因数，就不可能有更大的因数对。复杂度从 O(n) 降到 O(√n)。

② 质因数分解：从小到大试，试到一个就除掉

for (long long i = 2; i * i <= n; i++) {
 while (n % i == 0) {
 printf("%lld ", i); // i 是一个质因数
 n /= i; //  除干净再试下一个
 }
}
if (n > 1) printf("%lld\n", n); //  剩下的这个也是质因数（大于 sqrt 的那个）

最后那句 if (n > 1) printf(n) 是必写的一步，漏了就丢掉了最大的那个质因数。

③ 常用结论（客观题和编程题都会用）

④ 埃氏筛模板（一次求出一堆质数）

bool notPrime[N + 1] = {false};
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 开始

埃氏筛的逐步划数过程（从 2 开始，每遇没被划掉的数就划掉它的倍数）：

⑤ 提高级数论工具：费马小定理与威尔逊定理（大纲 2.5.2）

判质数除了试除和筛法，提高级还会用到两个同余定理（注意它们只能作辅助判质，费马小定理对卡迈克尔数会误判，不能单独当判质函数用）：

• 费马小定理：若 p 是质数且 p ∤ a，则 a^(p-1) ≡ 1 (mod p)。重要推论：模质数 p 下 a 的逆元 a⁻¹ ≡ a^(p-2) (mod p)，用快速幂 O(log p) 即可求出（这是组合计数里除了「扩欧求逆」之外的标准做法，前提是 a 不是 p 的倍数）。
• 威尔逊定理：(p-1)! ≡ −1 (mod p) 当且仅当 p 为质数。可双向使用——既能由质数算出 (p-1)! mod p，也能反过来据此判断 p 是否为质数（但 p 稍大时 (p-1)! 算不动，实用性有限，重在认识结论、应对选择填空）。

⑥ 线性筛（欧拉筛）：每个合数只被最小质因子划掉一次（考纲要求）

埃氏筛会被同一个合数用它的多个质因子重复划掉（如 12 被 2、3 各划一次），复杂度 O(N log log N)。提高级要求的线性筛让每个合数只被最小质因子划一次，达到 O(N)：

int primes[N], cnt; // 质数表
bool notPrime[N + 1] = {false};
for (int i = 2; i <= N; i++) {
 if (!notPrime[i]) primes[cnt++] = i; // i 是质数，收进质数表
 for (int j = 0; j < cnt; j++) {
 if (1LL * i * primes[j] > N) break; // 越界停止（乘前判越界，防 int 溢出）
 notPrime[i * primes[j]] = true; // 划掉 i*primes[j]，其最小质因子就是 primes[j]
 if (i % primes[j] == 0) break; // 关键：i 已含 primes[j] 就停，保证只被最小质因子划
 }
}

那句 if (i % primes[j] == 0) break 是精髓：轮到 primes[j] 划掉 i*primes[j] 后，若 i 本身已经含有因子 primes[j]，再用更大的质数去划就会让该合数被「非最小质因子」划到——于是立即停。线性筛还能顺带 O(N) 求出每个数的最小质因子、欧拉函数 φ，是数论预处理的主力。埃氏筛与线性筛的对比见下：

技巧速查表（背下来）

例题

题目 1：质因数分解的完整输出

题目描述

给定一个正整数 $n$（$1 \le n \le 10^{12}$），请将其分解为质因数的乘积形式，并按从小到大的顺序输出所有质因数。例如，若 $n=360$，应输出 2 2 2 3 3 5。注意：如果 $n=1$，不需要输出任何数字。

审题分析

• 输入范围 $10^{12}$ 意味着不能暴力枚举到 $n$，必须利用试除法只枚举到 $\sqrt{n}$（即 $10^6$ 级别），这是可行的。
• 题目要求输出“所有质因数”，这意味着如果某个质因数出现了多次（如 $2^3$），必须输出多次。
• 边界情况 $n=1$ 需要特殊处理，因为 1 既不是质数也没有质因数。
• 为什么能用本知识点？因为核心操作就是从小到大试除，一旦整除就除干净（while 循环），这正是质因数分解的标准流程。
• 如果不用本知识点？比如用埃氏筛预处理到 $10^6$ 的质数表，虽然也可以，但代码更冗长且对于单次查询来说，直接试除更简洁高效。

解题思路

1. 特判 $n=1$，直接结束。

2. 从 $i=2$ 开始循环，条件是 $i \times i \le n$。

3. 在循环内部，用 while 不断检查 $n \% i == 0$，如果成立，就打印 $i$ 并将 $n$ 除以 $i$。这一步保证了同一个质因数会被连续打印多次。

4. 循环结束后，如果剩下的 $n > 1$，说明它本身是一个大于 $\sqrt{\text{原}n}$ 的质因数，需要打印。

5. 注意使用 long long 防止 $i \times i$ 溢出。

C++ 完整参考代码

#include <iostream>
using namespace std;

int main() {
 long long n;
 // 1. 读取输入
 if (!(cin >> n)) return 0;

 // 2. 边界情况：1 没有质因数，直接退出
 if (n == 1) {
 return 0;
 }

 // 3. 从小到大试除，i*i <= n 保证只枚举到 sqrt
 for (long long i = 2; i * i <= n; i++) {
 // 4. while 循环确保把同一个质因数除干净（例如 8=2^3 会输 2,2,2）
 while (n % i == 0) {
 cout << i << " ";
 n /= i;
 }
 }

 // 5. 循环结束后，如果 n > 1，说明剩下的是最大的那个质因数
 if (n > 1) {
 cout << n;
 }

 cout << endl;
 return 0;
}

代码解读

• i * i <= n 是试除法的核心，复杂度降为 $O(\sqrt{n})$。
• while (n % i == 0) 是关键，如果用 if 只能除一次，无法处理 $2^3$ 这样的情况。
• 最后的 if (n > 1) 是必写的收尾步骤，漏掉就会丢失最大的质因数。
• 运行结果（输入 360）：

```

2 2 2 3 3 5

```

这与题目要求的输出完全一致。

题目 2：判断质数与统计数量

题目描述

给定一个整数 $m$（$1 \le m \le 100$），请判断 $m$ 是否为质数。如果是，输出 Yes；否则输出 No。注意：$1$ 不是质数。

审题分析

• 范围很小，直接试除即可。
• 必须特判 $m < 2$ 的情况。
• 为什么能用本知识点？因为质数定义就是只有 1 和它本身两个因数，试除到 $\sqrt{m}$ 找不到其他因数即为质数。
• 如果不用本知识点？可以用埃氏筛预处理，但对于单个数判断来说，试除法代码更短且足够快。

解题思路

1. 读入 $m$。

2. 如果 $m < 2$，直接输出 No。

3. 否则，从 $2$ 循环到 $\sqrt{m}$，一旦整除就输出 No 并退出。

4. 循环结束仍未找到因数，输出 Yes。

C++ 完整参考代码

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

int main() {
 long long m;
 if (!(cin >> m)) return 0;

 if (m < 2) {
 cout << "No" << endl;
 return 0;
 }

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

 if (isPrime) cout << "Yes" << endl;
 else cout << "No" << endl;

 return 0;
}

代码解读

• 逻辑清晰，先排除 0 和 1。
• 循环条件 i * i <= m 自动处理了平方数的情况。
• 运行结果（输入 17）：

```

Yes

```

（输入 1）：

```

No

```

例题复盘总结

共性特征

• 所有题目都围绕“质数”或“因数”展开，核心操作是试除到 √n。
• 输出要求往往涉及“分解”或“判断”，需要严格处理边界（如 1 不是质数，分解完剩下的 n 也要输出）。

各自技巧

• 分解题：必须用 while 循环除干净，且最后补 if (n > 1)。
• 判断题：先特判 <2，再试除。
• 哥德巴赫类（虽未出例题，但属于本知识点）：枚举小质数，利用 isPrime 判断大数。

审题模板

1. 数据范围多大？只判几个数 → 试除法；要判很多数 → 筛法。

2. 要的是“判断”还是“分解”还是“枚举约数”？三个需求写法不同。

3. 有没有“2 很特殊”的提示？出现“偶质数”“两质数之和为偶数”，答案往往就靠“2 是唯一偶质数”。

4. 要不要用 long long？i * i 是典型溢出点。

5. 分解完记得补最后那个 n > 1 —— 漏了就丢了最大质因数。

错误清单

• 1 和 0 没特判（1 不是质数）。
• 试除只到 n/2（虽然也对，但 O(n) 远慢于 O(√n)）。
• 分解完忘了最后那个 n > 1。
• while 写成 if（同一个质因数可能重复出现多次）。
• i * i 溢出（用 int 时 i 到 46341 就爆了）。
• 筛法从 i 开始标记而不是 i * i（多做无用功）。
• 筛法数组开小了（要求 1..N 的质数就要开 notPrime[N + 1]）。
• 用 n % 2 == 0 判断偶数就说是合数（忘了 2 本身是质数）。

写法总表

分工说明：触发清单告诉你“什么时候想到它”，速查表告诉你“想做什么时写哪段代码”，本表则按技法粒度从细到粗梳理写法。

常见错误

1. 1 和 0 没特判。 1 不是质数！if (n < 2) return false; 这一句不能省。

2. 试除只到 n/2。 虽然也对，但 O(n) 远慢于 O(√n)。**一定要写 i * i <= n**。

3. 分解完忘了最后那个 n > 1。 丢掉了最大的质因数（最常见的失分点）。

4. while 写成 if。 同一个质因数可能重复出现多次（如 8 = 2³），必须用 while 除干净。

5. **i * i 溢出。 用 int 时 i 到 46341 就爆了。i 和 n 都用 long long。**

6. **筛法从 i 开始标记而不是 i * i。** 从 i 开始会多做很多无用功（虽然结果对，但更慢）；从 i*i 开始更好。

7. 筛法数组开小了。 要求 1..N 的质数就要开 notPrime[N + 1]。

8. 用 n % 2 == 0 判断偶数就说是合数。 忘了 2 本身是质数。

自测

1. 为什么判断质数只需要试到 √n？

2. 写出质因数分解的循环，并说明为什么最后要写 if (n > 1)。

3. 为什么分解时同一质因数的处理要用 while 而不是 if？

举一反三 · 审题流水线

拿到一道数论题，先问自己五个问题：

1. 数据范围多大？只判几个数 → 试除法；要判很多 → 筛法。

2. 要的是“判断”还是“分解”还是“枚举约数”？

3. 有没有“2 很特殊”的提示？

4. 要不要用 long long？

5. 分解完记得补最后那个 n > 1 吗？

练手题

题目 A：区间质数个数

给定两个整数 $L, R$（$1 \le L \le R \le 10^6$），请统计区间 $[L, R]$ 内有多少个质数。

提示：数据范围允许直接筛，但要注意 $L$ 可能很小，$R$ 可能很大，考虑用埃氏筛预处理到 $R$ 后，用前缀和数组快速回答查询。

题目 B：最大质因数

给定一个整数 $n$（$1 \le n \le 10^{12}$），请输出它的最大质因数。

提示：直接分解后，记录每次除掉的质因数，最后剩下的 $n$（如果大于 1）就是最大的。注意特判 $n=1$ 的情况，此时没有质因数，输出 0。