信息学奥赛 2032 题解：分解质因数 3 种解法与 2 个常见错误分析
在信息学竞赛中，分解质因数是一个经典且重要的算法问题。它不仅考察选手对数学基础的理解，还检验编程实现的能力。本文将深入探讨三种不同的解法，并分析初学者容易犯的两个典型错误。
1. 问题理解与基础解法
分解质因数的核心任务是将一个正整数表示为一系列质数的乘积形式。例如，数字60可以分解为2×2×3×5。这个问题看似简单，但在编程实现时需要考虑效率和正确性。
1.1 循环解法
最直观的方法是使用循环从最小的质数开始尝试分解：
#include <iostream> using namespace std; void factorize(int n) { int i = 2; cout << n << "="; bool first = true; while (n > 1) { if (n % i == 0) { if (!first) cout << "*"; cout << i; n /= i; first = false; } else { i++; } } } int main() { int n; cin >> n; factorize(n); return 0; }关键点分析：
- 从2开始逐个尝试除数
- 当找到一个因数时，立即除以该因数并保持i不变
- 使用first标志控制乘号的输出
1.2 效率优化
基础循环解法的时间复杂度为O(n)，对于大数效率较低。我们可以进行以下优化：
- 仅检查到√n：因为n的因数成对出现，大于√n的因数必然对应一个小于√n的因数
- 跳过偶数：在检查完2后，可以只检查奇数
优化后的代码：
void factorize_optimized(int n) { cout << n << "="; bool first = true; // 处理2的因数 while (n % 2 == 0) { if (!first) cout << "*"; cout << 2; n /= 2; first = false; } // 检查奇数 for (int i = 3; i * i <= n; i += 2) { while (n % i == 0) { if (!first) cout << "*"; cout << i; n /= i; first = false; } } // 处理剩余的质数 if (n > 1) { if (!first) cout << "*"; cout << n; } }2. 递归解法
递归方法提供了一种更优雅的实现方式，它将问题分解为更小的子问题：
#include <iostream> using namespace std; void factorize_recursive(int n, int i = 2, bool first = true) { if (n == 1) return; if (n % i == 0) { if (!first) cout << "*"; cout << i; factorize_recursive(n / i, i, false); } else { factorize_recursive(n, i + 1, first); } } int main() { int n; cin >> n; cout << n << "="; factorize_recursive(n); return 0; }递归特点：
- 每次递归调用处理一个质因数
- 保持当前尝试的除数和是否是第一个因数的状态
- 当n变为1时终止递归
3. 质数表优化法
对于需要多次分解质因数的情况，预先计算质数表可以显著提高效率：
3.1 质数表生成
首先需要生成一定范围内的质数表，常用的方法有：
- 普通筛法（埃拉托斯特尼筛法）
- 线性筛法（欧拉筛法）
这里展示普通筛法的实现：
vector<int> generate_primes(int limit) { vector<bool> is_prime(limit + 1, true); vector<int> primes; for (int p = 2; p * p <= limit; ++p) { if (is_prime[p]) { for (int i = p * p; i <= limit; i += p) { is_prime[i] = false; } } } for (int p = 2; p <= limit; ++p) { if (is_prime[p]) primes.push_back(p); } return primes; }3.2 使用质数表分解
void factorize_with_primes(int n, const vector<int>& primes) { cout << n << "="; bool first = true; for (int p : primes) { if (p * p > n) break; while (n % p == 0) { if (!first) cout << "*"; cout << p; n /= p; first = false; } } if (n > 1) { if (!first) cout << "*"; cout << n; } }优势分析：
- 预处理质数表后，分解效率显著提高
- 特别适合需要多次分解不同数字的场景
- 质数表可以预先计算并存储
4. 常见错误分析
在实现分解质因数算法时，初学者常会遇到以下两类错误：
4.1 输出格式错误
错误表现：
- 多输出乘号，如"12=22*3"
- 少输出乘号，如"12=223"
- 输出顺序不正确
正确做法：
- 使用标志变量控制第一个因数的输出
- 确保每个非第一个因数前都有乘号
- 严格按照从小到大的顺序输出
// 正确输出格式示例 void correct_output(int n) { cout << n << "="; bool first = true; for (int i = 2; i <= n; ++i) { while (n % i == 0) { if (!first) cout << "*"; cout << i; n /= i; first = false; } } }4.2 大数处理溢出
问题场景：
- 当n接近INT_MAX时，i*i可能导致整数溢出
- 使用递归时，深度过大导致栈溢出
解决方案：
- 使用long long类型存储大数
- 修改循环条件避免溢出：
for (long long i = 2; i <= n / i; ++i) { // 分解逻辑 }- 对于递归解法，可以转换为迭代实现避免栈溢出
5. 算法选择与性能对比
不同解法在不同场景下的表现：
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 基础循环 | O(n) | O(1) | 小规模数据 |
| 优化循环 | O(√n) | O(1) | 中等规模数据 |
| 递归 | O(n) | O(n)调用栈 | 教学演示 |
| 质数表 | O(π(√n)) | O(√n) | 需要多次分解 |
实际测试数据：
- 对于n=1,000,000，优化循环比基础循环快约1000倍
- 质数表方法在重复分解时优势明显，首次分解因需要生成质数表而稍慢
6. 竞赛应用技巧
在编程竞赛中，质因数分解常与其他算法结合使用：
- 最大公约数/最小公倍数计算
- 约数个数统计
- 欧拉函数计算
- 模运算相关问题
实用技巧：
- 预处理质数表可以大幅提升后续分解速度
- 结合试除法和Miller-Rabin素性测试处理极大数
- 使用记忆化存储已分解结果
// 预处理质数表示例 const int MAX = 1e6; vector<int> primes; void precompute() { vector<bool> is_prime(MAX + 1, true); for (int p = 2; p * p <= MAX; ++p) { if (is_prime[p]) { for (int i = p * p; i <= MAX; i += p) { is_prime[i] = false; } } } for (int p = 2; p <= MAX; ++p) { if (is_prime[p]) primes.push_back(p); } }在实际比赛中，我通常会先预处理质数表，这样在需要多次分解时可以节省大量时间。对于特别大的数，结合Pollard's Rho算法会更高效。
