Prime factorization
This simple C program finds the unique prime factorization of nonnegative integers.
C code
/* Find the unique prime factorization
Version 1.2 (2019-01-05, revised 2019-03-04) */
/* Standard header file for fprintf, fputs, printf, puts */
#include <stdio.h>
/* Standard header file for EXIT_FAILURE, EXIT_SUCCESS, free, malloc, NULL, realloc */
#include <stdlib.h>
/* Standard header file for strcmp */
#include <string.h>
/* Standard header file for sqrt */
#include <math.h>
/* Returns the position of a character in a character array */
unsigned char position_in_character_array (char const character)
{
char const character_array [] = "0123456789ABCDEFabcdef";
unsigned char position = 0;
while ((character_array [position] != character) && (character_array [position] != 0))
{
position ++;
}
return position;
}
/* Returns the maximum position of a character in a character array across all characters in a string */
unsigned char maximum_position_in_character_array (char const * const string)
{
unsigned char position = 0;
unsigned char maximum_position = 0;
while ((string [position] != 0) && (maximum_position < 22))
{
unsigned char character_array_position = position_in_character_array (string [position]);
if (character_array_position > maximum_position)
{
maximum_position = character_array_position;
}
position ++;
}
return maximum_position;
}
/* Sets the default base indicator */
unsigned char default_base_indicator (int const argument_count, char const * const argument_array [])
{
unsigned char base_indicator = 'u';
unsigned char const zero = 1 << 0;
unsigned char const base_8 = 1 << 1;
unsigned char const uppercase_base_16_with_prefix = 1 << 2;
unsigned char const lowercase_base_16_with_prefix = 1 <<3;
unsigned char const uppercase_base_16_without_prefix = 1 << 4;
unsigned char const lowercase_base_16_without_prefix = 1 << 5;
unsigned char const ambiguous_base = 1 << 6;
unsigned char const found_base = 1 << 7;
unsigned char status = 0;
int argument_index;
for (argument_index = 1; argument_index < argument_count; argument_index ++)
{
char const * const string = argument_array [argument_index];
unsigned long int position = 0;
unsigned char maximum_position;
if (string [position] == '-')
{
position ++;
}
if (string [position] == '0')
{
position ++;
if (string [position] == 0)
{
status |= (found_base | zero);
}
else if ((string [position] != 'O') && (string [position] != 'o') && (string [position] != 'X') && (string [position] != 'x'))
{
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position <8)
{
status |= (found_base | base_8);
}
else if (maximum_position < 10)
{
status |= (found_base | ambiguous_base);
}
else if (maximum_position < 16)
{
status |= (found_base | uppercase_base_16_without_prefix);
}
else if (maximum_position < 22)
{
status |= (found_base | lowercase_base_16_without_prefix);
}
}
}
if ((status & found_base) == 0)
{
if ((string [position] == 'O') || (string [position] == 'o'))
{
position ++;
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position <8)
{
status |= base_8;
}
}
else if ((string [position] == 'X') || (string [position] == 'x'))
{
position ++;
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position < 16)
{
status |= uppercase_base_16_with_prefix;
}
else if (maximum_position < 22)
{
status |= lowercase_base_16_with_prefix;
}
}
else
{
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position < 10)
{
status |= ambiguous_base;
}
else if (maximum_position < 16)
{
status |= uppercase_base_16_without_prefix;
}
else if (maximum_position < 22)
{
status |= lowercase_base_16_without_prefix;
}
}
}
else
{
status &= ~ found_base;
}
}
if ((status == base_8) || (status == (zero | base_8)))
{
base_indicator = 'o';
}
else if ((status & lowercase_base_16_without_prefix) != 0)
{
base_indicator = 'x';
}
else if ((status & uppercase_base_16_without_prefix) != 0)
{
base_indicator = 'X';
}
else if ((status == lowercase_base_16_with_prefix) || (status == (uppercase_base_16_with_prefix | lowercase_base_16_with_prefix)))
{
base_indicator = 'x';
}
else if (status == uppercase_base_16_with_prefix)
{
base_indicator = 'X';
}
else
{
base_indicator = 'u';
}
return base_indicator;
}
/* Returns the value corresponding to the position of the character in the character array */
unsigned char value (unsigned char position)
{
unsigned char return_value;
if (position > 15)
{
return_value = position - 6;
}
else
{
return_value = position;
}
return return_value;
}
/* Converts a string representing an integer into an integer */
unsigned long long int string_as_integer (char const * const string, unsigned char const base_indicator, unsigned char * const error)
{
unsigned char const false = 0;
unsigned char const true = 1;
unsigned char negative = false;
unsigned long int position = 0;
unsigned char maximum_position;
unsigned char base = 0;
unsigned long long int integer = 0;
* error = 0;
if (string [position] == '-')
{
negative = true;
position ++;
}
if (string [position] == '0')
{
position ++;
if (string [position] == 0)
{
base = 1;
}
else if ((string [position] != 'O') && (string [position] != 'o') && (string [position] != 'X') && (string [position] != 'x'))
{
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position <8)
{
base = 8;
}
else if ((maximum_position < 10) && (base_indicator != 'X') && (base_indicator != 'x'))
{
base = 10;
}
else if (maximum_position < 22)
{
base = 16;
}
else
{
* error = 1;
}
}
}
if (base == 0)
{
if ((string [position] == 'O') || (string [position] == 'o'))
{
position ++;
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position <8)
{
base = 8;
}
else
{
* error = 8;
}
}
else if ((string [position] == 'X') || (string [position] == 'x'))
{
position ++;
maximum_position = maximum_position_in_character_array (& (string [position]));
if (maximum_position < 22)
{
base = 16;
}
else
{
* error = 16;
}
}
else
{
maximum_position = maximum_position_in_character_array (& (string [position]));
if ((maximum_position < 22) && ((base_indicator == 'X') || (base_indicator == 'x')))
{
base = 16;
}
else if (maximum_position < 10)
{
base = 10;
}
else if (maximum_position < 22)
{
base = 16;
}
else
{
* error = 1;
}
}
}
if (base > 0)
{
while ((string [position] > 0) && (* error == 0))
{
unsigned long long int previous_integer = integer;
if (integer > 0)
{
integer *= base;
}
integer += value (position_in_character_array (string [position]));
if ((previous_integer != 0) && (integer <= previous_integer))
{
* error = 255;
}
position ++;
}
if (negative == true)
{
integer = (- integer);
}
}
return integer;
}
unsigned long int int_sqrt (unsigned long long int input)
{
unsigned long int const maximum_unsigned_long_int = -1;
unsigned long long int result = sqrt (input);
if (result > maximum_unsigned_long_int)
{
result = maximum_unsigned_long_int;
}
return result;
}
int main (int const argument_count, char const * const argument_array [])
{
int return_value = EXIT_SUCCESS;
char const * const program_file_name = argument_array [0];
unsigned char const option_help = 1 << 0;
unsigned char const option_version = 1 << 1;
char const * const option_string_array [] = { "?", "/?", "/H", "/h", "-?", "-H", "-h", "-help", "--help", "--version" };
unsigned char const option_value_array [] = { option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_help, option_version };
unsigned char const option_string_count = sizeof (option_string_array) / sizeof (option_string_array [0]);
unsigned char const option_value_count = sizeof (option_value_array) / sizeof (option_value_array [0]);
unsigned char status = 0;
if (option_string_count != option_value_count)
{
unsigned char option_index;
fprintf (stderr, "%s: Internal error: The size of the option value array (%u) does not match the size of the option string array (%u)\n", program_file_name, option_value_count, option_string_count);
fputs ("index: value, string\n", stderr);
for (option_index = 0; (option_index < option_string_count) && (option_index < option_value_count); option_index ++)
{
fprintf (stderr, "%u: %u, %s\n", option_index, option_value_array [option_index], option_string_array [option_index]);
}
if (option_string_count > option_value_count)
{
for (option_index = option_value_count; option_index < option_string_count; option_index ++)
{
fprintf (stderr, "%u: [none], %s\n", option_index, option_string_array [option_index]);
}
}
else
{
for (option_index = option_string_count; option_index < option_value_count; option_index ++)
{
fprintf (stderr, "%u: %u, [none]\n", option_index, option_value_array [option_index]);
}
}
return_value = EXIT_FAILURE;
}
else
{
int argument_index;
/* Set options */
for (argument_index = 1; (argument_index < argument_count) && (status == 0); argument_index ++)
{
char const * const current_argument = argument_array [argument_index];
unsigned char const valid_option = 1 << 2;
unsigned char option_index;
status &= ~ valid_option;
for (option_index = 0; (option_index < option_string_count) && ((status & valid_option) == 0); option_index ++)
{
if (strcmp (option_string_array [option_index], current_argument) == 0)
{
status |= valid_option;
status |= option_value_array [option_index];
}
}
}
/* Print information */
if ((status & option_help) != 0)
{
printf ("Usage: %s [list of nonnegative integers separated by spaces]\n", program_file_name);
puts ("Print the unique prime factorization for each integer from the lowest integer in the list to the highest integer in the list.");
}
else if ((status & option_version) != 0)
{
puts ("Find unique prime factorizations 1.2");
}
else
{
/* Read the arguments that are integers */
unsigned char base_indicator = default_base_indicator (argument_count, argument_array);
unsigned int integer_count = 0;
unsigned long long int minimum_integer = 0;
unsigned long long int maximum_integer = 0;
for (argument_index = 1; argument_index < argument_count; argument_index ++)
{
unsigned char error = 0;
unsigned long long int integer = string_as_integer (argument_array [argument_index], base_indicator, & error);
if (error == 0)
{
integer_count ++;
if (integer_count == 1)
{
minimum_integer = integer;
maximum_integer = integer;
}
else if (integer < minimum_integer)
{
minimum_integer = integer;
}
else if (integer > maximum_integer)
{
maximum_integer = integer;
}
}
else
{
char * message;
if (error == 1)
{
message = "Invalid integer";
}
else if (error == 8)
{
message = "Invalid octal integer";
}
else if (error == 16)
{
message = "Invalid hexadecimal integer";
}
else if (error == 255)
{
message = "Integer is too large";
}
else
{
message = "Unknown error";
}
fprintf (stderr, "%s: %s: %s\n", program_file_name, message, argument_array [argument_index]);
return_value = EXIT_FAILURE;
}
}
/* Set the print format strings */
char long_long_integer_format_string [] = "%llu = ";
char long_prime_with_power_format_string [] = "%lu ^ %hhu\n";
char long_prime_with_power_and_product_format_string [] = "%lu ^ %hhu * ";
char long_long_prime_format_string [] = "%llu ^ 1\n";
long_long_integer_format_string [3] = base_indicator;
long_prime_with_power_format_string [2] = base_indicator;
long_prime_with_power_format_string [9] = base_indicator;
long_prime_with_power_and_product_format_string [2] = base_indicator;
long_prime_with_power_and_product_format_string [9] = base_indicator;
long_long_prime_format_string [3] = base_indicator;
if (maximum_integer > 1)
{
unsigned char const false = 0;
unsigned char const true = 1;
/* Create an array to store some prime numbers */
unsigned long int upper_bound_for_primes = int_sqrt (maximum_integer);
if ((upper_bound_for_primes > 2) && ((upper_bound_for_primes % 2) == 0))
{
upper_bound_for_primes --;
}
if ((upper_bound_for_primes > 3) && ((upper_bound_for_primes % 3) ==0))
{
upper_bound_for_primes -= 2;
}
unsigned long int prime_array_size = ((upper_bound_for_primes - 1) / 3) + 2;
unsigned long int * prime_array;
/* The initial size of the array of prime numbers is likely to be too large, so we can try a smaller size if we cannot allocate enough memory for the initial size */
while ((prime_array_size > 0) && ((prime_array = malloc (prime_array_size * sizeof (unsigned long int))) == NULL))
{
prime_array_size *= 0.9;
}
/* Find prime numbers and store them in the array */
unsigned long int candidate = 2;
unsigned long int prime_count = 0;
unsigned char found_enough_primes = false;
unsigned char step = 4;
unsigned short int upper_bound_for_square_roots = int_sqrt (upper_bound_for_primes);
unsigned short int square_root = 0;
/* Store the first two prime numbers */
if (prime_array_size > 0)
{
prime_array [prime_count] = candidate;
prime_count ++;
candidate = 3;
if (prime_array_size > 1)
{
prime_array [prime_count] = candidate;
prime_count ++;
candidate = 5;
/* Find more prime numbers */
while ((prime_count < prime_array_size) && (found_enough_primes == false))
{
/* We have found enough primes if we have reached the last candidate */
if (candidate >= upper_bound_for_primes)
{
found_enough_primes = true;
}
else if (step == 2)
{
/* Adjust the step size to skip the odd numbers greater than 5 that are equal to 3 mod 6, because they are divisible by 3 */
step = 4;
}
else
{
step = 2;
}
/* Calculate the square root of the candidate */
while ((square_root < upper_bound_for_square_roots) && ((((1ul * square_root) + 1) * (square_root + 1)) <= candidate))
{
square_root ++;
}
/* Test whether any of the prime numbers that are less than the square root of the canddidate divide the candidate. We need not test whether the prime numbers 2 or 3 divide the candidate, because we have only considered candidates that are not divisible by 2 or 3. */
unsigned char found_factor = false;
unsigned long int prime_counter;
for (prime_counter = 2; (found_factor == false) && (prime_counter < prime_count) && (prime_array [prime_counter] <= square_root); prime_counter ++)
{
if ((candidate % (prime_array [prime_counter])) == 0)
{
/* Found a factor, so the candidate is not prime */
found_factor = true;
}
}
if (found_factor == false)
{
/* Did not find a factor, so the candidate is prime and we can add it to the array */
prime_array [prime_count] = candidate;
prime_count ++;
}
candidate += step;
}
}
}
if (found_enough_primes == false)
{
/* When we have not found enough prime numbers, reduce the maximum integer */
unsigned long long int new_maximum_integer = ((1ull * candidate) * candidate) - 1;
if (new_maximum_integer < maximum_integer)
{
fprintf (stderr, "%s: Unable to allocate enough memory to store all the necessary primes, so reducing the maximum integer to %llu\n", program_file_name, new_maximum_integer);
return_value = EXIT_FAILURE;
maximum_integer = new_maximum_integer;
}
}
else if (prime_array_size > prime_count)
{
/* When we have found enough prime numbers, try to reduce the size of the array, so that it is only as large as we need */
void * new_prime_array;
prime_array_size = prime_count;
new_prime_array = realloc (prime_array, prime_array_size * sizeof (unsigned long int));
if ((new_prime_array != NULL) && (new_prime_array != prime_array))
{
prime_array = new_prime_array;
}
}
/* Create an array to store the square of each prime number */
unsigned long long int * squared_prime_array = malloc (prime_count * sizeof (unsigned long long int));
if (squared_prime_array != NULL)
{
unsigned long int prime_counter;
for (prime_counter = 0; prime_counter < prime_count; prime_counter ++)
{
squared_prime_array [prime_counter] = (1ull * prime_array [prime_counter]) * prime_array [prime_counter];
}
}
/* Find prime factors */
if (minimum_integer < 2)
{
if (minimum_integer == 0)
{
puts ("0 = 0");
}
if (maximum_integer >= 1)
{
puts ("1 = 1");
}
minimum_integer = 2;
}
unsigned long long int integer = minimum_integer;
unsigned char reached_maximum = false;
for (integer = minimum_integer; reached_maximum == false; integer ++)
{
if (integer == maximum_integer)
{
reached_maximum = true;
}
unsigned long int prime_counter = 0;
printf (long_long_integer_format_string, integer);
unsigned long long int result = integer;
while ((result > 1) && (prime_counter < prime_count) && (((squared_prime_array != NULL) && (squared_prime_array [prime_counter] <= result)) || ((squared_prime_array == NULL) && (((1ull * prime_array [prime_counter]) * prime_array [prime_counter]) <= result))))
{
if ((result % (prime_array [prime_counter])) == 0)
{
unsigned char power = 1;
result /= prime_array [prime_counter];
while ((result % (prime_array [prime_counter])) == 0)
{
power ++;
result /= prime_array [prime_counter];
}
if (result == 1)
{
printf (long_prime_with_power_format_string, prime_array [prime_counter], power);
}
else
{
printf (long_prime_with_power_and_product_format_string, prime_array [prime_counter], power);
}
}
prime_counter ++;
}
if (result > 1)
{
printf (long_long_prime_format_string, result);
}
}
if (squared_prime_array != NULL)
{
free (squared_prime_array);
squared_prime_array = NULL;
}
if (prime_array != NULL)
{
free (prime_array);
prime_array = NULL;
}
}
}
}
return return_value;
}