唯一分解定理，也被称为算术基本定理，是数论中一个基础而重要的定理。它说明了任何一个大于 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 为例，对比进阶版的执行过程：
唯一分解定理的重要性体现在多个方面：
遇到因数分解相关问题时，按以下步骤思考：
i < n 而不是 i <= sqrt(n)：这会导致时间复杂度从 O(sqrt(n)) 退化到 O(n)，对于大数会超时。i * i <= n 代替 i <= sqrt(n)，或者将 sqrt 结果转为整数后加 1 作为上界。