fyzx92 - 1 month ago 5

C Question

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

- finding greatest prime factor using recursion in c :This question is about crashing code. Mine compiles, runs, and produces reasonably sensible output, I'm just wondering why the output isn't what I expect.
- is there ever a time you would not use recursion? [closed] :This indicates that recursion is not a good choice for prime factorization- I don't know, but suspect that this would also apply to C. Since this is for reference, I don't think it is a huge issue. If you disagree, please explain why.

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*.