CODEWITHSUNDEEP
c++recursion
Quaker
Quaker

Reputation: 1553

A recursive function to print the prime factoring element of an integer

I need to write a recursive function to print the prime factoring elements of an integer, ascending.

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);
    }
}

What am I doing wrong? My output, for 20 is:

5 2 5 2 2

My smallest input is a prime number and a smaller input for the recursive function is num div (smallest prime divider of num).

Upvotes: 2

Views: 4486

Answers (2)

Bill Lynch
Bill Lynch

Reputation: 81916

NPE has provided a (tail) recursive version, here's the iterative version:

What we do here is:

  1. Our first possible divisor is 2. Try that value.
  2. If it divides the number evenly, then print the divisor, and divide our target number by that divisor.
  3. If it doesn't divide, then try the next divisor. div += 1.

Note that we don't increment div when it does divide. This is because of cases like 20, where 2 divides it multiple times.

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

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

Upvotes: 1

NPE
NPE

Reputation: 500187

I believe the following will work:

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);
        }
}

As requested, it is recursive, even though recursion isn't necessary and can be trivially converted into iteration.

The reason your original version doesn't quite work is twofold:

  1. the printing is misplaced, which results in the factors being printed in descending order;
  2. after the recursive call you keep trying further divisors, which results in the duplicate factors appearing on the output.

Upvotes: 5

Related Questions