质因数分解算法原理与C++实现优化

1. 分解质因数算法解析

质因数分解是数论中的基础算法，也是信息学竞赛中的常见考点。这个算法的核心思想是将一个合数表示为若干个质数相乘的形式。比如数字12可以分解为2×2×3。

1.1 算法原理

质因数分解基于算术基本定理：任何大于1的自然数，要么本身是质数，要么可以唯一分解为质数的乘积。算法实现的关键在于：

1. 从最小的质数2开始尝试
2. 如果能整除当前数，则记录这个质因数
3. 不断用当前数除以该质数，直到不能整除为止
4. 然后尝试下一个更大的数

这个过程中有几个优化点：

• 不需要单独判断某个数是否为质数，因为合数会被更小的质因数提前分解
• 循环只需要到√n即可，因为大于√n的因数必然对应一个小于√n的因数

1.2 代码实现分析

让我们仔细分析提供的C++实现代码：

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

int main() {
    int n;
    cin >> n;
    cout << n << "=";
    bool flag = true;
    for (int i = 2; i <= n; i++) {
        while (n % i == 0) {
            if (!flag) {
                cout << "*";
            }
            cout << i;
            n = n / i;
            flag = false;
        }
    }
}

这段代码有几个值得注意的实现细节：

1. 使用flag变量控制乘号的输出，确保第一个因数前不输出乘号
2. while循环确保将当前质因数完全除尽
3. 每次成功分解后更新n的值，缩小问题规模

2. 算法优化与改进

2.1 循环终止条件优化

原始代码的循环条件是i <= n，但实际上当i > √n时，如果n还没被分解为1，那么剩下的n一定是质数。因此可以优化为：

cpp复制for (int i = 2; i * i <= n; i++) {
    while (n % i == 0) {