c++快速分解质因数算法

C++中可以使用欧几里得算法（Euclidean Algorithm）为基础，结合循环结构来实现快速分解质因数。这是一种比较常见且高效的算法，也称为辗转相除法。以下是基本步骤：

1. **选择最大公约数**：从输入的数字开始，选择一个初始的大于1的因子作为“当前”因子（如数字本身），然后不断除以这个因子和余数的最大公约数。

2. **更新因子**：如果余数不是1，说明找到了一个非平凡的因子，将它加入结果列表，并更新当前因子为之前的余数。

3. **继续除法**：直到找到的余数为1为止，这时最后一个非平凡的因子就是原数的一个质因数。接着对剩下的部分（即之前除以最后的非平凡因子后的值）重复上述过程，直至所有质因数都被找到。

下面是简化的C++代码示例：

#include <iostream>
#include <vector>

// 辗转相除求最大公约数
int gcd(int a, int b) {
    while (b != 0) {
        int t = a % b;
        a = b;
        b = t;
    }
    return a;
}

// 分解质因数
std::vector<int> primeFactorization(int n) {
    std::vector<int> factors;
    for (int i = 2; i * i <= n; ++i) { // 只需检查到√n
        while (n % i == 0) {
            factors.push_back(i);
            n /= i; // 更新n为去除i后的值
        }
    }

    // 如果n大于1（表示n本身就是质数）
    if (n > 1)
        factors.push_back(n);

    return factors;
}

int main() {
    int num;
    std::cout << "请输入一个整数: ";
    std::cin >> num;

    std::vector<int> result = primeFactorization(num);
    std::cout << "质因数分解结果: [";
    for (const auto &factor : result) {
        std::cout << factor << ", ";
    }
    std::cout << "]" << std::endl;

    return 0;
}