Hello I am dire need of help. I have gone to many different variations some code but I can't seem to come up with a solution. The code is suppose to do this:
Write a function that finds all the prime factors of a number N, stores it to an array and returns a pointer to that array.(The returned memory will be freed for you in the main.) Also, since the length of the array is unknown a priori, it is convenient to terminate the array of factors with a 0.
It is remarkable that in order to find prime factors with recursion you do not need to use the helper functionisPrime from one of the previous labs to decide if numbers are prime (nor should you!).

Can someone verbally explain to me step by step how to create a function that does this?

2. Code:
```int main(int argc, char *argv[]){
int M, *x, *p, y[101], m, i;
double k;
sscanf(argv[1], "%d", &M);
/*
//test sumPowers
k = 1.0;
printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));
k = 3.4;
printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));
k = 5.123;
printf("Power of first %d integers to %lf is %lf\n",M,k, sumPowersRec(M,k));

//test saveMoney
printf("Money saved after %d years with initial deposit \$1000,\n annual deposits \$100 and interest rate 0.01 is \$%lf\n",M, saveMoney(1000,100, 0.01,M));
printf("Money saved after %d years with initial deposit \$5234,\n annual deposits \$600 and interest rate 0.02 is \$%lf\n",M, saveMoney(5234,600, 0.02,M));
printf("Money saved after %d years with initial deposit \$123,\n  annual deposits \$45 and interest rate 0.0067 is \$%lf\n",M, saveMoney(123,45, 0.0067,M));
printf("Money saved after %d years with initial deposit \$34567,\n annual deposits \$9876 and interest rate 0.00567 is \$%lf\n",M, saveMoney(34567,9876, 0.00576,M));

//test Pascal's triangle
for(m=0; m <= M; m++)
{
pascalsTriangle(y, m);
for(i=0; i<(M-m)*2; i++)  printf(" ");
for(p = y; p <= y+m; p++)
printf("%4d", *p);
printf("\n");
}
*/
//test prime factors
x = primeFactors(M);
for(p = x; *p != 0; p++)
printf("%d  ", *p);
printf("\n");
free(x);
return 0;```
The main function looks like that.

3. Code:
``` int *primeFactors(int N){
int nAlloc =1, i, *p;
int *x = (int *)malloc(2*nAlloc*sizeof(int));

if(N==1)
{
x[0] =1;
x[1] = 2;
}
for(i = 2; i <= N/2; i++)
{
if((N%i)==0)
{
nAlloc =+1;
x[nAlloc] = i;
x = realloc(x,nAlloc*sizeof(int));
x =primeFactors(N/i);
}
}
return p;```

4. Do you know how to factor a number into primes your own self (without a computer)? If so, well, that's basically your algorithm sorted.

5. But with it comes to malloc and realloc, I basically keep on overwriting the values and all that prints is an empty array

6. So what purpose does p have in your code?

7. If I was doing this problem I'd probably begin by doing it without worrying about storing it in array; i.e. just recursively print out the prime factors (from within the primefactors function). After that's working properly I'd then move onto storing the results in an array.

Edit: I should have added that your recursive function (ignoring the memory/array issue) is currently incorrect.

8. Since I had nothing to do I went ahead and implemented your function. I won't post the function here but this is my main() with tests... it may be helpful in some way. I'm not suggesting that you use this main function in your submission but it may help you test.

To be safe you'd really want to test a whole bunch of numbers, but I leave that to you (I feel I've done too much already, but as I said I was bored)

Code:
```#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main(void)
{
int *pfacts, n, product;

n = 12345678;

pfacts = primefactors(n);

if (pfacts && pfacts[0] != 0) {
size_t pos;
product = 1;
for (pos = 0; pfacts[pos] != 0; pos++) {
assert(isPrime(pfacts[pos]));              /* Each factor must be prime */
printf("Factor: %d\n", pfacts[pos]);
product *= pfacts[pos];
}

/* The product of the factors must equal the original number */

printf("\nProduct is: %d\n", product);
printf("Product test %s\n", product == n ? "passed." : "FAILED!");
}
free(pfacts);

return 0;
}```

9. Originally Posted by Casanova411
It is remarkable that in order to find prime factors with recursion you do not need to use the helper function isPrime from one of the previous labs to decide if numbers are prime (nor should you!).
It's not quite so remarkable, and the helper function isPrime would not be needed if you found the prime factors with iteration either.

Are you sure this function is to be implemented via recursion? If so, it's going to be somewhat inefficient compared to an iterative approach.

10. Either the OP solved this or gave up. Here's an example that creates the array in reverse order. It's not efficient, but it is recursive.

Code:
```#include <stdio.h>
#include <stdlib.h>

int * FindFactors(int n){
int *p;
int i, j;
if(n < 2){
p = malloc(sizeof(int));
p[0] = 0;
return p;
}
for(i = 2; i <= n; i++){
if((n%i) == 0){
n /= i;
p = FindFactors(n);
for(j = 0; p[j]; j++);
p = realloc(p, (j+2)*sizeof(int));
p[j] = i;
p[j+1] = 0;
return(p);
}
}
return(NULL);   /* this statement never reached */
}

int main(){
int *p, *q;
q = p = FindFactors(120);
while(*p){
printf("%3d ", *p);
p++;
}
printf("\n");
free(q);
return 0;
}```

11. Originally Posted by rcgldr
Either the OP solved this or gave up. Here's an example that creates the array in reverse order. It's not efficient, but it is recursive.
Well, I kind of "cheated" by using a wrapper. Plus it's a mess... oh well

Code:
```#include <stdio.h>
#include <stdlib.h>

int primefactors_r(unsigned n, int **mem, size_t *sz)
{
int i, maxn;

if (n < 2)
return 0;

maxn = n / 2;
for (i = 2; i <= maxn; i++) {
if (n % i == 0) {
if (primefactors_r(i, mem, sz)) {
(*mem)[*sz - 1] = i;
*mem = realloc(*mem, ++(*sz) * sizeof(**mem));
}
if (primefactors_r(n / i, mem, sz)) {
(*mem)[*sz - 1] = n / i;
*mem = realloc(*mem, ++(*sz) * sizeof(**mem));
}
break;
}
}
/* return 0 (false) if no 'lower' primefactors found;
* i.e. the above loop didn't terminate early */
return i > maxn;
}

int *primefactors(unsigned n)
{
int *mem = NULL;
size_t sz = 1;

if ((mem = malloc(sizeof *mem * sz)) == NULL)
return NULL;

if (n < 4) {
mem[0] = 0;
return mem;
}

primefactors_r(n, &mem, &sz);
if (mem) {
mem[sz - 1] = 0;
}
return mem;
}

int main(void)
{
int *pfacts, n, product;

n = 120;

pfacts = primefactors(n);

if (pfacts && pfacts[0] != 0) {
size_t pos;
product = 1;
for (pos = 0; pfacts[pos] != 0; pos++) {
printf("Factor: %d\n", pfacts[pos]);
product *= pfacts[pos];
}
printf("\nProduct is: %d\n", product);
printf("Product test %s\n", product == n ? "passed." : "FAILED!");
}
free(pfacts);

return 0;
}```