CODEWITHSUNDEEP
c++
Obamaa
Obamaa

Reputation: 33

Prime Factorization Using Recursion

My program currently outputs the prime factorization of a positive integer in ascending order. I'm trying to figure out how to set up the function so that it outputs the numbers in descending order.

For example, showFactors(100) currently outputs "2 2 5 5".

Instead I want it to output "5 5 2 2".

 10 // Void function "showFactors" that takes in an int "number" and another     int "factor", which is initialized to 2
 11 void showFactors(int number, int factor = 2)
 12 {
 13
 14   if (number<2) //returns nothing if number<2
 15   {
 16     return;
 17   }
 18   if (number%factor==0) //modulus function is used to get prime  factorization
 19   {
 20     cout<<factor<<" ";
 21     showFactors(number/factor, factor); //recursive call
 22   }
 23   else //if (number%factor != 0) //this modulus function is used in order to output factor !=2  
 24   {
 25     showFactors(number, factor+1);
 26   }
 27 }

I feel like there should be an easy fix by simply rearranging where the cout call goes, but I haven't had any luck so far.

Edit: Yeah it was as simple as switching lines 20 and 21.

Upvotes: 2

Views: 5187

Answers (3)

masterleo
masterleo

Reputation: 19

//ECMAscript oneliner to find prime factors using recursion
const pf = (n, f=2, A=[]) => !~-n ? A : n%f ? pf(n,++f,A) : pf(n/f,f,[...A,f])

//example
console.log(pf(60));

Upvotes: 0

chety
chety

Reputation: 156

Here is my Ruby solution to get a list of prime factors of a given number. Maybe it will help someone

def prime_factorization(num)
    (2...num).each do |fact|
        if (num % fact == 0)
            otherFact = num / fact
            return [ *prime_factorization(fact), *prime_factorization(otherFact) ]
        end
    end

    return [num]
end

Upvotes: 0

Rohith R
Rohith R

Reputation: 1329

#include <iostream>
using namespace std;
void sf (int number,int factor=2)
{
    if (number<2)
        return;
    if (number%factor == 0)
    {
        sf (number/factor,factor);
        cout<<factor<<"\t";
    }
    else
        sf (number,factor+1);
}

int main ()
{
    sf (1729);
    cout<<"\n";

    return 0;
}

Upvotes: 5

Related Questions