如何在质因数分解递归函数中仅执行一次is_prime检查？

你的问题核心是递归过程中重复执行了初始的质数检查，导致分解到最后一个质数时触发了错误提示。要实现“仅执行一次初始检查，后续递归跳过该检查”的需求，同时满足每次调用质因数分解相关函数时都调用is_prime，可以用拆分函数的方式，把初始检查和递归分解逻辑分开，既清晰又符合要求。

修改后的代码 #

#include <iostream>
using namespace std;

bool is_prime(int input){
    bool prime = true;
    if(input == 0 || input ==1){
        prime = false;
    }
    for (int i = 2; i <= input/2; i++) {
        if (input % i == 0) {
            prime = false;
            break;
        }
    }
    return prime;
}

// 内部递归辅助函数：负责质因数分解，每次调用会通过is_prime判断剩余数
void prime_factorization_helper(int input){
    int num = 2;
    // 找到第一个质因数
    while(input % num != 0) num++;
    cout << num << " ";
    int remaining = input / num;
    // 判断剩余数是否为质数，这里调用了is_prime
    if(is_prime(remaining)){
        cout << remaining << endl;
    } else {
        prime_factorization_helper(remaining);
    }
}

// 对外入口函数：仅做一次初始质数检查
void prime_factorization(int input){
    if(is_prime(input)){
        cout << "That is a prime number" << endl;
    } else {
        prime_factorization_helper(input);
    }
}

// 测试示例
int main(){
    prime_factorization(14); // 输出：2 7
    prime_factorization(7);  // 输出：That is a prime number
    return 0;
}

逻辑说明 #

1. 入口函数prime_factorization：只在第一次调用时执行is_prime检查，如果输入本身是质数，直接打印提示；否则调用辅助函数开始分解。
2. 辅助函数prime_factorization_helper：专注于质因数分解，每次递归时都会调用is_prime判断剩余数值是否为质数——如果是，直接输出该质数结束分解；如果不是，继续递归分解剩余数值。
3. 对于输入14的场景：入口函数判断14不是质数，调用辅助函数找到第一个质因数2并输出，剩余数值7通过is_prime判断为质数，直接输出7，最终结果为2 7，符合预期。

内容的提问来源于stack exchange，提问作者ibucksss