本课时有配套视频讲解，购买后即可观看（永久有效）
因数分解
一、课上练习
编程练习
二、知识总结
✨ 核心思想
唯一分解定理，也被称为算术基本定理，是数论中一个基础而重要的定理。它说明了任何一个大于 1 的自然数都可以被写作若干个质数（素数）的乘积，并且这种分解方式除了因数的顺序外是唯一的。这个定理是数论的基石之一，为处理数字的质因数分解提供了理论基础。
✨ 唯一分解的表示
唯一分解定理可以具体表述为：对于任何一个大于 1 的整数 n，它可以表示为：
n = p1^k1 p2^k2 ... * pm^km
其中 p1, p2, ..., pm 是不同的质数，而 k1, k2, ..., km 是对应的正整数指数。此外，这种表示除了质数的顺序外没有其他不同的方式。
例如，60 = 2^2 3^1 5^1，这是 60 唯一的质因数分解形式。
✨ 因数分解的实现（普通版）
普通版的因数分解从 2 开始，依次尝试每个可能的因子直到 sqrt(n)。对于每个因子，反复除尽后记录该因子及其出现次数：
因数分解代码示例（普通版）
1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6struct Factor {
7 int base;
8 int exponent;
9};
10
11// 函数用于分解质因数
12void factorize(int n) {
13 // 用于存储质因数和它们的次数（对于每个质因数，第一个元素是质因数，第二个元素是次数）
14 vector<Factor> factors;
15
16 int count = 0; // 用于计数因数的个数
17 // 从2开始，每次检查是否能被n整除
18 for (int i = 2; i <= sqrt(n); i++) {
19 count = 0; // 重置计数器
20 while (n % i == 0) {
21 count++;
22 n /= i; // 除以i，减小n的值
23 }
24 // 如果count大于0，说明找到了一个质因数
25 if (count > 0) {
26 factors.push_back(Factor{i, count});
27 }
28 }
29
30 // 如果n此时大于2，说明n本身是一个质数
31 if (n > 2) {
32 factors.push_back(Factor{n, 1});
33 }
34
35 // 输出分解结果
36 for (int i = 0; i < factors.size(); i++) {
37 cout << factors[i].base << "^" << factors[i].exponent << " ";
38 }
39}
40
41int main() {
42 int number;
43 cout << "Enter a positive integer: ";
44 cin >> number; // 输入一个正整数
45
46 cout << "Prime factorization of " << number << " is: ";
47 factorize(number); // 调用函数分解质因数
48
49 return 0;
50}✨ 执行示例
以分解 360 的质因数为例：
初始值：n = 360，sqrt(360) ≈ 18.97
| 步骤 | 当前i | n能被i整除？ | 操作 | n的变化 | 记录的因子 |
|---|---|---|---|---|---|
| 1 | i=2 | 360%2=0 是 | 除以2 | 360→180 | count=1 |
| 2 | i=2 | 180%2=0 是 | 除以2 | 180→90 | count=2 |
| 3 | i=2 | 90%2=0 是 | 除以2 | 90→45 | count=3 |
| 4 | i=2 | 45%2=1 否 | 记录 2^3 | n=45 | factors: {2,3} |
| 5 | i=3 | 45%3=0 是 | 除以3 | 45→15 | count=1 |
| 6 | i=3 | 15%3=0 是 | 除以3 | 15→5 | count=2 |
| 7 | i=3 | 5%3=2 否 | 记录 3^2 | n=5 | factors: {2,3},{3,2} |
| 8 | i=4 | 4 > sqrt(5)≈2.23 | 循环结束 | - | - |
| 9 | - | n=5 > 2 | 记录 5^1 | - | factors: {2,3},{3,2},{5,1} |
最终结果：360 = 2^3 × 3^2 × 5^1
✨ 因数分解的实现（进阶版）
进阶版在普通版的基础上进行了优化：先单独处理因子 2，将 n 除尽所有的 2 之后，n 就变成了奇数，接下来只需从 3 开始、每次加 2 来检查奇数因子，从而将循环次数减少一半：
因数分解代码示例（进阶版）
1#include <iostream>
2#include <vector>
3#include <cmath>
4using namespace std;
5
6struct Factor {
7 int base;
8 int exponent;
9};
10
11// 函数用于分解质因数
12void factorize(int n) {
13 // 用于存储质因数和它们的次数（对于每个质因数，第一个元素是质因数，第二个元素是次数）
14 vector<Factor> factors;
15
16 // 处理所有的2，确保n是奇数
17 int count = 0; // 用于计数2的个数
18 while (n % 2 == 0) {
19 count++;
20 n /= 2;
21 }
22 // 如果count大于0，说明n能被2整除
23 if (count > 0) {
24 factors.push_back(Factor{2, count});
25 }
26
27 // n此时是奇数，从3开始，每次加2检查是否能被n整除
28 for (int i = 3; i <= sqrt(n); i += 2) {
29 count = 0; // 重置计数器
30 while (n % i == 0) {
31 count++;
32 n /= i; // 除以i，减小n的值
33 }
34 // 如果count大于0，说明找到了一个质因数
35 if (count > 0) {
36 factors.push_back(Factor{i, count});
37 }
38 }
39
40 // 如果n此时大于2，说明n本身是一个质数
41 if (n > 2) {
42 factors.push_back(Factor{n, 1});
43 }
44
45 // 输出分解结果
46 for (int i = 0; i < factors.size(); i++) {
47 cout << factors[i].base << "^" << factors[i].exponent << " ";
48 }
49}
50
51int main() {
52 int number;
53 cout << "Enter a positive integer: ";
54 cin >> number; // 输入一个正整数
55
56 cout << "Prime factorization of " << number << " is: ";
57 factorize(number); // 调用函数分解质因数
58
59 return 0;
60}✨ 执行示例
同样以 360 为例，对比进阶版的执行过程：
- 先单独处理因子 2：360→180→90→45，记录 2^3
- n=45 是奇数，从 i=3 开始、每次 +2：
- i=3：45→15→5，记录 3^2
- i=5：5 > sqrt(5)，循环结束
- n=5 > 2，记录 5^1
- 进阶版只检查了 i=3 这一个奇数因子（加上预处理的 2），而普通版检查了 i=2,3,4 共三个因子，效率更高。
✨ 唯一分解的重要性
唯一分解定理的重要性体现在多个方面：
- 基础性：它是许多数论性质和算法的基础，例如最大公约数和最小公倍数的计算，质数测试，以及在密码学中的应用。
- 理论支持：它为理解整数的结构和性质提供了理论支持，是进行更复杂数论研究的基础。
- 算法设计：在算法设计和密码学中，质数和它们的性质是核心要素。例如，RSA 加密算法就基于大数分解的困难性，而这又依赖于对唯一分解定理的理解。
✨ 解题步骤详解
遇到因数分解相关问题时，按以下步骤思考：
- 确定分解方法：一般情况用普通版就够了。如果 n 很大（接近 10^9），使用进阶版可以减少约一半的循环次数。
- 从最小质因数开始：从 2 开始尝试，每次把当前质因数除尽后再尝试下一个。这样自然保证了找到的都是质因数（不会遇到合数因子，因为更小的质因数已经被除尽）。
- 只需循环到 sqrt(n)：如果循环结束后 n 仍大于 1，说明剩余的 n 本身就是一个质因数。
- 记录因子和指数：使用结构体或 pair 存储每个质因数及其出现次数。
✨ 常见错误
- 循环条件写成
i < n而不是i <= sqrt(n)：这会导致时间复杂度从 O(sqrt(n)) 退化到 O(n)，对于大数会超时。 - 忘记处理循环结束后 n > 1 的情况：例如分解 14 时，除掉因子 2 后 n=7，此时 i=3 > sqrt(7)，循环结束，但 7 本身是一个质因数，如果忘记记录就会丢失。
- 每次 while 循环后不重置 count：导致多个因子的指数被累加，结果错误。
- 使用浮点数的 sqrt 导致精度问题：建议用
i * i <= n代替i <= sqrt(n)，或者将 sqrt 结果转为整数后加 1 作为上界。 - 没有考虑 n=1 的情况：1 没有质因数分解，应该特殊处理或不输出任何因子。
三、课后练习
编程练习
- 分解质因数：L3064