# Prime Factors (32 bits, without Sieve)

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


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

• 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. Dec 17 '16 at 0:37
• What causes for (; num > 1; ++primes) { to end? num is never changed and there are no break/return. Dec 17 '16 at 5:15
• @chux I think there's an implied (unstated) division statement in the while loop of vnp's remarkably concise code. Dec 17 '16 at 6:16
• @chux See edit. Shame on me.
– vnp
Dec 17 '16 at 7:35
• 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. Dec 17 '16 at 13:55