用于打印整数的素数因子元素的递归函数

Question

我需要编写一个递归函数来打印整数的素数因子元素,升序.

void printPrimeFactors(int num)
{
int div;

if (isPrime(num) == true)
    cout << num << " ";

else
{
    for (div = 2; div < num; div++)
    {
        if (isPrime(div) == true && num%div == 0)
            printPrimeFactors(num/div);
    }
}

我究竟做错了什么？我的输出,20为:

5 2 5 2 2

我的最小输入是素数,递归函数的输入较小num div (smallest prime divider of num).

Answer 1

我相信以下内容可行:

void printPrimeFactors(int num, int div = 2)
{
        if (num % div == 0) {
                std::cout << div << " ";
                printPrimeFactors(num / div, div);
        } else if (div <= num) {
                printPrimeFactors(num, div + 1);
        }
}

根据要求,它是递归的,即使递归不是必需的,并且可以简单地转换为迭代.

您的原始版本不能正常工作的原因有两个:

1. 打印错位,导致因素按降序打印;
2. 在递归调用之后,您继续尝试进一步的除数,这会导致输出中出现重复因子.