fyzx92 fyzx92 - 1 month ago 5
C Question

Recursively finding prime factors

I am starting to teach myself C and am trying to build a group of useful functions and programs for future reference. If relevant, this is C99.

Here is my most recent iteration of the program. At the output, I want to get the prime factorization of a number n. As is, however, I get a list of all factors, and no factors are repeated. I included some print statements to try and debug, and have found that the error is with the recursion, but can't figure out how to interpret it further. I previously tried making the recursive function of type int, but had difficulties getting it to work with the array p.


  • n is the number that I am trying to factor

  • p is an array for storing the found primes

  • j is an index for p

  • c is the number that I am testing as a divisor to n



I am aware that there are probably more efficient ways to declare p to save memory, but since this is mainly for reference, memory is not a huge concern.

I found these questions but don't think that they answer my question



My main questions are these:
Why does the output show all factors of n?
Why does it not repeat the prime factors?
What do I have to do to fix it?

#include <stdio.h>

#define NELEMS(x) (sizeof(x) / sizeof((x)[0]))

void factors(int n, int p[], int j) {
/// if n is divisible by c, store c, and continue with n/c
int c;
for (c=2; c < n; c++) {
if (c > n) break;
if (n%c == 0) {
p[j] = c;
printf("%d has been added to p \t", c);
printf("n has been reduced to %d \t", n/c);
printf("j is %d \n", j);
j++;
if (n == c) break;
factors(n/c, p, j);
}
}
}

int main() {
/// set up number to factor, and array to hold factors
int n = 24;
int p[n/2];
int i=0;
for (i=0; i<NELEMS(p); i++) {
p[i]=0;
}

int j = 0;
factors(n, p, j);

printf("the prime factors of %d are:\n",n);
for (i=0; i<NELEMS(p); i++) {
printf("%d \n", p[i]);
}

}

Answer Source

You have already been told in comments that this algorythm is poor, which is an evidence here. And you really should learn to use a debugger: running this through a debugger immediately shows where the problems are.

That being said, your main problem here is what to do when the recursive functions return?. You failed to ask yourself this question which is a must in recursion, and simply continue in sequence, which is plain wrong because you will reuse a number that has already been processed in the recursive calls. So you must add a return line immediately after recursively calling factors.

Once this is done, there is another minor problem (that a debugger would make evident), you only search factors strictly lesser that n. So you miss the last prime factor...

With those 2 immediate fixes, your code becomes:

void factors(int n, int p[], int j) {
  /// if n is divisible by c, store c, and continue with n/c
      int c;
      for (c=2; c <= n; c++) {
          if (c > n) break;
          if (n%c == 0) {
              p[j] = c;
              printf("%d has been added to p \t", c);
              printf("n has been reduced to %d \t", n/c);
              printf("j is %d \n", j);
              j++;
              if (n == c) break;
              factors(n/c, p, j);
              return;
          }
      }
  }

But IMHO p[j] = c; should become *p = c; and factors(n/c, p, j); should become factors(n/c, p+1, j);. Said differently you pass directly a pointer to the next slot.