Prime Factors (32 bits, without Sieve)

Question

I wrote this prime factors program as a programming exercise.

Any comments or constructive criticisms are welcome.

One question: prime[] is an array which stores the number's prime factors and associated exponents. How many elements, at most, does this array require? That is, what is the greatest number of prime factors needed to express any number between 1 and 4294967295? As an example 750 would need 3 elements since 750 = 2 * 3 * 5 ^ 3. I could do an exhaustive test using a static variable to keep track of the maximum value of pIndex but the 2.4 billion numbers would take at least 12 hours on my single core machine. Is there a quicker way to determine the answer?

/* primeexponents.c

   display a number's prime factors using exponents and also its number of
   divisors

   note: unsigned 32 bit numbers (1 - 4294967295)
*/

#include <stdio.h>
#include <stdbool.h>

void primeExponents (unsigned long int number, unsigned int list[])
{
    printf ("\nnumber = %lu\n", number);

    struct
    {
        unsigned long int factor;
        int exponent;
    } prime[20] = { { 0, 0 } };

    unsigned long int num = number;
    int pIndex = 0, lIndex = 0;

    prime[pIndex].factor = (unsigned long int) list[lIndex];

    while ( prime[pIndex].factor <= num / prime[pIndex].factor ) {
        if ( num % prime[pIndex].factor == 0 ) {
            ++prime[pIndex].exponent;
            num /= prime[pIndex].factor;
        }
        else {
            if ( prime[pIndex].exponent > 0 ) 
                ++pIndex;
            ++lIndex;
            prime[pIndex].factor = (unsigned long int) list[lIndex];
        }
    }

    // num = greatest prime factor

    if ( num == prime[pIndex].factor )
        ++prime[pIndex].exponent;
    else {
        if ( prime[pIndex].exponent > 0 )
            ++pIndex;
        prime[pIndex].factor = num;
        prime[pIndex].exponent = 1;
    }

    printf ("prime factors =");

    unsigned long int product = 1;
    int divisors = 1;

    for ( int i = 0; i <= pIndex; ++i ) {
        printf (" %lu", prime[i].factor);
        if ( prime[i].exponent > 1 )   
            printf (" ^ %i", prime[i].exponent);
        if ( i < pIndex )
            printf (" *");
        // calculate product of prime factors to verify result
        for ( int j = 1; j <= prime[i].exponent; ++j )
            product *= prime[i].factor;
        // calculate number of divisors
        divisors *= prime[i].exponent + 1;
    }
    printf ("\n");

    printf ("product of prime factors = %lu", product);
    if ( product != number )
        printf (" <<< error >>>");
    printf ("\n");

    printf ("divisors = %i\n\n", divisors);
}

void generateList (unsigned int list[])
{
    // generate a list of prime numbers to use as trial factors, i.e.
    // list[0] = 2, [1] = 3, [2] = 5, [3] = 7, [4] = 11, ... [6541] = 65521

    bool isPrime;
    list[0] = 2;
    list[1] = 3;
    int index = 2;

    for ( unsigned int i = 5; i <= 65535; i += 2 ) {
        isPrime = true;

        for ( int j = 1; (i / list[j] >= list[j]) && isPrime; ++j ) {
            if ( i % list[j] == 0 ) 
                isPrime = false;
        }

        if ( isPrime ) {
            list[index] = i;
            ++index;
        }    
    }        
}

int main (void)
{
    printf ("\nPrime Factors with Exponents Program\n\n");

    unsigned int list[6542];

    generateList (list);

    unsigned long int number;

    do {
        printf ("enter a number (from 1 to 4294967295, 0 to exit): ");
        scanf ("%lu", &number);

        if ( number != 0 )
            primeExponents (number, list);
    }
    while ( number != 0 );

    return 0;
}

Answer 1

You don't need an exhaustive search: \$2*3*5*7*11*13*17*19*23*29 = 6469693230 > 2^{32}\$, so it is safe to allocate 9 slots.

---

primeExponents does too much and shall be split into three functions, one to factorize a number, another to validate factorization, and yet another to print it.

---

The factorization logic is extremely hard to follow. Consider instead

void factorize(int num, factors_t * factors, int * primes)
{ 
  for (; num > 1; ++primes) {
    factors->prime = *primes;
    factors.exponent = 0;

    while (num % *primes == 0) {
      factors->exponent++;
      num /= **primes; // Edit: shame on me.
    }

    if (factors->exponent > 0) {
      factors++;
    }
  }
}