user6788452 user6788452 - 2 months ago 6
C Question

Factorization in C-Recursion

I've been asked to write a void function in c(no loops), that gets an even number(lets say 80), and prints it like this
2*2*5*2*2
As you can see the result is 80 lol.
Between 2 numbers you need to print "*", and the odd number(for my example,5) you need to print it in the middle, or if there is an odd numbers of "2" in the number, lets say 96 you need to print it like that:2*2*2*3*2*2
If the given number is odd, return the number.
I whould like to get not only te answer, but the way you "think" before starting to code.
Here is what i got so far

if(n%4==0)
{
printf("2*");
PrintTwos(n/4);
return;
}
if(n%2==0)
{
printf("*2");
PrintTwos(n/2);
return;
}
printf("%d",n);

Answer

here is some pseudo code:

func(nbr)
  isOdd(nbr)         // recursive stop condition
    print nbr
    return

  evenNbr = findFirstEven(nbr)  //return the shortest even number from nbr
  print evenNbr
  func(nbr / evenNbr)

I didn't add logic for the * printing because i'm sure u can figure that about by yourself. And one case will break that pseudo code, but that's a good start to help you thinking about what your recursive function should do.

EDIT following comments: (NOT COMPLETE : odd number in the middle is missing in this)

int findFirstEven(nbr, i) {
    if (nbr%i != 0)
      return findFirstEven(nbr, i++);
    return i;
}

int primefact(int n)
{
    int i=2;
    i = findFirstEven(n, i);

    printf("%d*", i);
    if(n==i)
        printf("1");
        return 0;
    else
        primefact(n/i);
}

(not tested)