基于最小质因子函数编写C++递归程序实现正整数质因数分解

云原生阿岚

2026-10-5

实现思路

你已经实现的smallFactor函数逻辑完全正确，无需修改，我们只需要新增符合要求的递归函数即可，原来的isPrime函数可以直接删除
递归函数的核心逻辑分为两个分支：
1. 递归终止条件：调用smallFactor获取当前数的最小质因数，如果这个值等于当前数本身，说明当前数已经是质数，直接输出它即可结束递归
2. 递归推进逻辑：如果最小质因数不等于当前数，先输出这个最小质因数，然后将当前数除以该最小质因数，用得到的新值作为参数再次调用递归函数

完整可运行代码

#include <iostream>
using namespace std;

int smallFactor(int);
void printPrimeFactors(int); // 递归函数声明

int main()
{
    int posInt;

    cout << "Enter one positive integer: ";
    cin >> posInt;
    cout << "The prime factors of " << posInt << " are ";

    printPrimeFactors(posInt);
    cout << endl;

    return 0;
}

// 你已实现的最小质因数计算函数
int smallFactor(int posInt)
{
    if (posInt % 2 == 0)
        return 2;

    for (int i = 3; i * i <= posInt; i += 2)
    {
        if (posInt % i == 0)
            return i;
    }

    return posInt;
}

// 新增递归打印所有质因数的函数
void printPrimeFactors(int n) {
    int minPrime = smallFactor(n);
    if (minPrime == n) {
        cout << minPrime;
        return;
    }
    cout << minPrime << " ";
    printPrimeFactors(n / minPrime);
}