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