c++ - 用于打印整数的素数分解元素的递归函数

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. 在递归调用之后，您继续尝试进一步的除数，这会导致输出中出现重复的因子。

Answer 2

NPE 提供了一个（尾）递归版本，这里是迭代版本：

我们在这里做的是：

1. 我们的第一个可能的除数是 2。试试这个值。
2. 如果它将数字除以均匀，则打印除数，并将我们的目标数除以该除数。
3. 如果它不除，然后尝试下一个除数。div += 1.

div请注意，当它除法时我们不会增加。这是因为像20, where2多次划分它的情况。

void printPrimeFactors(int num) {
    int div = 2;

    while (num != 1) {
        if (num % div == 0) {
            cout << num << " ";
            num /= div;
        } else {
            div += 1;
        }
    }
}