Thread: Recursion Madness

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?

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.

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;

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.

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

So what purpose does p have in your code?

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;
}

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;
}

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;
}