C++中如何求一个数的质因数分解

质因数分解指的是将一个大于1的整数分解为若干个素数相乘的形式，每个素数都是原数的质因数。在C++中实现质因数分解，核心思路是先找到能整除目标数的最小素数，记录该素数后，将目标数除以这个素数，重复这个过程直到目标数变为1。

基础版质因数分解实现

最基础的思路是从2开始遍历到目标数的平方根，依次判断当前数是否为目标数的因数，如果是则不断除尽该因数，记录结果。这种方法逻辑简单，适合处理数值较小的场景。

#include <iostream>
#include <vector>
using namespace std;

// 基础版质因数分解函数，返回存储质因数的vector
vector<int> primeFactorizationBasic(int n) {
    vector<int> factors;
    // 处理小于2的输入，小于2的数没有质因数
    if (n < 2) {
        return factors;
    }
    // 从2开始遍历到n的平方根
    for (int i = 2; i * i <= n; i++) {
        // 如果i能整除n，说明i是n的质因数
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    // 如果最后n大于1，说明剩下的n是质因数
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int main() {
    int num = 84;
    vector<int> res = primeFactorizationBasic(num);
    cout << num << "的质因数分解为：";
    for (size_t i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i != res.size() - 1) {
            cout << " * ";
        }
    }
    cout << endl;
    return 0;
}

上述代码中，遍历到i*i <= n是因为如果n有大于平方根的质因数，那么必然对应一个小于平方根的质因数，已经被提前处理过了。最后如果n还大于1，说明剩下的n本身就是一个大于平方根的质因数。

优化版质因数分解实现

基础版的问题在于会遍历很多非素数，比如4、6、8等，这些数不可能是质因数，遍历它们会浪费时间。优化思路是先预处理出一定范围内的素数，再用素数去试除目标数，减少不必要的遍历。

#include <iostream>
#include <vector>
using namespace std;

// 埃氏筛法生成素数表
vector<int> generatePrimes(int maxNum) {
    vector<bool> isPrime(maxNum + 1, true);
    vector<int> primes;
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i <= maxNum; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
            // 标记i的倍数为非素数
            for (int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return primes;
}

// 优化版质因数分解函数
vector<int> primeFactorizationOptimized(int n) {
    vector<int> factors;
    if (n < 2) {
        return factors;
    }
    // 生成n平方根范围内的素数表
    int maxPrime = 0;
    for (int i = 2; i * i <= n; i++) {
        maxPrime = i;
    }
    vector<int> primes = generatePrimes(maxPrime);
    // 用素数表中的素数试除
    for (int prime : primes) {
        while (n % prime == 0) {
            factors.push_back(prime);
            n /= prime;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int main() {
    int num = 120;
    vector<int> res = primeFactorizationOptimized(num);
    cout << num << "的质因数分解为：";
    for (size_t i = 0; i < res.size(); i++) {
        cout << res[i];
        if (i != res.size() - 1) {
            cout << " * ";
        }
    }
    cout << endl;
    return 0;
}

优化版通过埃氏筛法先得到素数表，只用素数去试除目标数，避免了遍历合数的开销，在处理较大数值的质因数分解时效率更高。如果目标数非常大，还可以结合米勒-拉宾素性检测等算法进一步优化素数判断的逻辑。

两种方案的对比

我们可以通过下表直观对比两种实现的特点：

实际开发中可以根据目标数的大小和运行环境的要求选择合适的实现方案，两种方案的核心逻辑都是不断找到能整除当前数的最小质因数，直到目标数被完全分解。

C++质因数分解算法素数修改时间：2026-07-23 13:06:27