质因数分解算法：从原理到竞赛实践

1. 问题背景与需求分析

1032题"分解质因数"是信息学奥赛入门阶段的经典数论题目。这道题考察的是选手对质数性质的理解和基础算法的实现能力。在实际比赛中，这类题目往往作为中等难度的基础题出现，需要选手在有限时间内完成代码编写。

质因数分解在密码学、数据压缩等领域有重要应用。比如RSA加密算法就依赖于大整数的质因数分解难度。虽然题目给出的数字范围不大（通常限制在2≤n≤10^6），但理解其原理对后续学习更高级算法至关重要。

2. 算法思路解析

2.1 质因数分解的基本原理

质因数分解的核心思想是将一个合数表示为若干个质数的乘积形式。根据算术基本定理，任何大于1的自然数都可以唯一地分解为质因数的乘积（不考虑顺序）。

例如：

• 12 = 2 × 2 × 3
• 28 = 2 × 2 × 7
• 97 = 97（本身就是质数）

2.2 试除法实现思路

最直观的质因数分解方法是试除法。其基本步骤如下：

1. 从最小的质数2开始尝试
2. 如果当前数能被该质数整除，则记录这个质因数，并将原数除以该质数
3. 重复步骤2直到不能再整除
4. 尝试下一个可能的质因数
5. 当剩余的数变为1时，分解完成

这个算法的时间复杂度主要取决于n的大小和质因数的大小，最坏情况下是O(√n)。

3. 代码实现详解

3.1 基础版本实现

cpp复制#include <iostream>
using namespace std;

void primeFactorization(int n) {
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            cout << i << " ";
            n /= i;
        }
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    primeFactorization(n);
    return 0;
}

这个基础版本虽然能正确分解质因数，但效率不高。因为它会尝试所有小于等于n的数，包括合数。

3.2 优化版本实现

我们可以做两个重要优化：

1. 只需要检查到