Prime numbers
This simple C program finds the prime numbers in a range.
C code
/* Find prime numbers
Version 1.3 (2019-01-25, 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;
}
/* If the input is clearly not prime, returns the nearest higher number that might be prime */
unsigned long long int upper_prime_candidate (unsigned long long int const input)
{
unsigned long long int candidate = input;
if (candidate < 2)
{
candidate = 2;
}
else
{
unsigned long long int const maximum_unsigned_long_long_int = 0xFFFFFFFFFFFFFF;
if ((candidate > 2) && ((candidate % 2) == 0))
{
candidate ++;
}
if ((candidate > 3) && (candidate < maximum_unsigned_long_long_int) && ((candidate % 3) ==0))
{
candidate += 2;
}
}
return candidate;
}
/* If the input is clearly not prime, returns the nearest lower number that might be prime */
unsigned long long int lower_prime_candidate (unsigned long long int const input)
{
unsigned long long int candidate = input;
if ((candidate > 2) && ((candidate % 2) == 0))
{
candidate --;
}
if ((candidate > 3) && ((candidate % 3) ==0))
{
candidate -= 2;
}
return candidate;
}
/* Returns the highest integer that is not greater than the square root of the input */
unsigned long int int_sqrt (unsigned long long int const input)
{
unsigned long int const maximum_unsigned_long_int = 0xFFFFFFFF;
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 each prime number that is greater than or equal to the lowest integer in the list and less than or equal to the highest integer in the list.");
}
else if ((status & option_version) != 0)
{
puts ("Find prime numbers 1.3");
}
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;
}
}
unsigned long long int first_candidate = upper_prime_candidate (minimum_integer);
unsigned long long int last_candidate = lower_prime_candidate (maximum_integer);
if (first_candidate <= last_candidate)
{
unsigned char const false = 0;
unsigned char const true = 1;
unsigned char reached_first_candidate = false;
if ((first_candidate <= 2) && (last_candidate >= 2))
{
reached_first_candidate = true;
puts ("2");
}
if ((first_candidate <= 3) && (last_candidate >= 3))
{
reached_first_candidate = true;
puts ("3");
}
if (last_candidate > 3)
{
unsigned short int const maximum_unsigned_short_int = 0xFFFF;
/* Set the print format strings */
char long_format_string [] = "%lu\n";
char long_long_format_string [] = "%llu\n";
long_format_string [2] = base_indicator;
long_long_format_string [3] = base_indicator;
/* Create an array to store some prime numbers */
unsigned long int last_candidate_for_prime_array = lower_prime_candidate (int_sqrt (last_candidate));
unsigned long int prime_array_size = (last_candidate_for_prime_array - 1) / 3;
unsigned long int * prime_array = NULL;
if (prime_array_size > 0)
{
/* 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;
}
}
unsigned long int candidate = 5;
unsigned short int short_prime_count = 0;
unsigned long int prime_count = 0;
unsigned char step = 0;
unsigned short int short_factor_candidate_count = 0;
unsigned long int square = candidate * candidate;
if (prime_array_size > 0)
{
/* Find prime numbers and store them in the array */
do
{
candidate += step;
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;
}
/* The maximum prime factor is not larger than the square root of the candidate */
while ((short_factor_candidate_count < short_prime_count) && (square <= candidate))
{
short_factor_candidate_count ++;
if (short_factor_candidate_count < prime_count)
{
square = (prime_array [short_factor_candidate_count ]) * (prime_array [short_factor_candidate_count ]);
}
}
/* 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 short int prime_counter;
for (prime_counter = 0; (found_factor == false) && (prime_counter < short_factor_candidate_count); 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 ++;
if (candidate <= maximum_unsigned_short_int )
{
short_prime_count ++;
}
}
}
while ((prime_count < prime_array_size) && (candidate < last_candidate_for_prime_array));
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;
}
}
if (prime_array [prime_count - 1] >= first_candidate)
{
reached_first_candidate = true;
unsigned long int prime_counter = 0;
while (prime_array [prime_counter] < first_candidate)
{
prime_counter ++;
}
while (prime_counter < prime_count)
{
printf (long_format_string, prime_array [prime_counter]);
prime_counter ++;
}
}
}
/* If we have not already reached the first candidate, start from the first candidate */
if (reached_first_candidate == false)
{
if ((first_candidate % 6) == 1)
{
step = 2;
}
else
{
step = 4;
}
}
unsigned long int const maximum_unsigned_long_int = 0xFFFFFFFF;
unsigned long int last_long_candidate = lower_prime_candidate (maximum_unsigned_long_int);
if (first_candidate <= last_long_candidate)
{
/* Find some more prime numbers */
if (reached_first_candidate == false)
{
candidate = first_candidate - step;
reached_first_candidate = true;
}
if (last_candidate < last_long_candidate )
{
last_long_candidate = last_candidate;
}
do
{
candidate += step;
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;
}
/* The maximum prime factor is not larger than the square root of the candidate */
while ((short_factor_candidate_count < short_prime_count) && (square <= candidate))
{
short_factor_candidate_count ++;
if (short_factor_candidate_count < prime_count)
{
square = (prime_array [short_factor_candidate_count ]) * (prime_array [short_factor_candidate_count ]);
}
}
/* 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 short int prime_counter;
for (prime_counter = 0; (found_factor == false) && (prime_counter < short_factor_candidate_count); 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) && (short_factor_candidate_count == prime_count) && (square <= candidate))
{
/* Try more potential factors, because the array does not contain enough prime numbers */
unsigned short int factor_candidate;
unsigned char factor_candidate_step;
unsigned short int last_factor_candidate = lower_prime_candidate (int_sqrt (candidate));
if (prime_count == 0)
{
factor_candidate = 0;
factor_candidate_step = 5;
}
else
{
factor_candidate = prime_array [prime_count - 1];
if ((factor_candidate % 6) == 1)
{
factor_candidate_step = 4;
}
else
{
factor_candidate_step = 2;
}
}
if (factor_candidate < last_factor_candidate)
{
do
{
factor_candidate += factor_candidate_step;
if ((candidate % factor_candidate) == 0)
{
/* Found a factor, so the candidate is not prime */
found_factor = true;
}
else if (factor_candidate_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 */
factor_candidate_step = 4;
}
else
{
factor_candidate_step = 2;
}
}
while ((found_factor == false) && (factor_candidate < last_factor_candidate));
}
}
if (found_factor == false)
{
/* Did not find a factor, so the candidate is prime */
printf (long_format_string, candidate);
}
}
while (candidate < last_long_candidate);
}
if (candidate < last_candidate)
{
unsigned long int long_factor_candidate_count = short_factor_candidate_count;
unsigned long long int long_long_square = square;
unsigned long long int long_long_candidate;
if (reached_first_candidate == false)
{
long_long_candidate = first_candidate - step;
}
else
{
long_long_candidate = candidate;
}
do
{
long_long_candidate += step;
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;
}
/* The maximum prime factor is not larger than the square root of the candidate */
while ((long_factor_candidate_count < prime_count) && (long_long_square <= long_long_candidate))
{
long_factor_candidate_count ++;
if (long_factor_candidate_count < prime_count)
{
long_long_square = (1ull * prime_array [long_factor_candidate_count ]) * (prime_array [long_factor_candidate_count ]);
}
}
/* 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 = 0; (found_factor == false) && (prime_counter < long_factor_candidate_count); prime_counter ++)
{
if ((long_long_candidate % (prime_array [prime_counter])) == 0)
{
/* Found a factor, so the candidate is not prime */
found_factor = true;
}
}
if ((found_factor == false) && (long_factor_candidate_count == prime_count) && (long_long_square <= long_long_candidate))
{
/* Try more potential factors, because the array does not contain enough prime numbers */
unsigned long int factor_candidate;
unsigned char factor_candidate_step;
unsigned long int last_factor_candidate = lower_prime_candidate (int_sqrt (long_long_candidate));
if (prime_count == 0)
{
factor_candidate = 0;
factor_candidate_step = 5;
}
else
{
factor_candidate = prime_array [prime_count - 1];
if ((factor_candidate % 6) == 1)
{
factor_candidate_step = 4;
}
else
{
factor_candidate_step = 2;
}
}
if (factor_candidate < last_factor_candidate)
{
do
{
factor_candidate += factor_candidate_step;
if ((long_long_candidate % factor_candidate) == 0)
{
/* Found a factor, so the candidate is not prime */
found_factor = true;
}
else if (factor_candidate_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 */
factor_candidate_step = 4;
}
else
{
factor_candidate_step = 2;
}
}
while ((found_factor == false) && (factor_candidate < last_factor_candidate));
}
}
if (found_factor == false)
{
/* Did not find a factor, so the candidate is prime */
printf (long_long_format_string, long_long_candidate);
}
}
while (long_long_candidate < last_candidate);
}
if (prime_array != NULL)
{
free (prime_array);
prime_array = NULL;
}
}
}
}
}
return return_value;
}