3
\$\begingroup\$

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;
}
\$\endgroup\$
2
\$\begingroup\$

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++;
    }
  }
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Your solution as to the maximum size for the array was what I had originally thought -- I didn't mention it so as to not bias an answer. Thanks. \$\endgroup\$ – Have Compiler -- Will Travel Dec 17 '16 at 0:37
  • \$\begingroup\$ What causes for (; num > 1; ++primes) { to end? num is never changed and there are no break/return. \$\endgroup\$ – chux - Reinstate Monica Dec 17 '16 at 5:15
  • \$\begingroup\$ @chux I think there's an implied (unstated) division statement in the while loop of vnp's remarkably concise code. \$\endgroup\$ – Have Compiler -- Will Travel Dec 17 '16 at 6:16
  • \$\begingroup\$ @chux See edit. Shame on me. \$\endgroup\$ – vnp Dec 17 '16 at 7:35
  • \$\begingroup\$ Perhaps num /= *primes; instead of num /= **primes;? Minor: also the closer num /= *primes; is to num % *primes, I suspect the more likely a compiler will use an optimization to effectively code these operations together as one div/rem. \$\endgroup\$ – chux - Reinstate Monica Dec 17 '16 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.