#### Home << Back

Small routine to compute all primes between 2 and N, being N a natural number bigger (>) than 2. Feel free to use this routine if you like it, but I will appreciate if you could let me know before using it.

#include "math.h"
#include "numbers.h"
#include "stdbool.h"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

/**
* Calculates a ^ (p - 1) % p. This routine produces overflows for
* exponents larger than 100,000.
*
* @param base     The base number.
* @param exponent The exponent.
* @param divisor  The divisor.
*
* @return The remainder of the division between a ^ (p - 1) and p.
*
* @author  Andreas P. Koenzen
* @version 0.1
*/
unsigned long long modulo(unsigned long long base,
unsigned long long exponent,
unsigned long long divisor) {
unsigned long long x = 1, y = base;
while (exponent > 0) {
if (exponent % 2 == 1) { x = (x * y) % divisor; }
y = (y * y) % divisor;
exponent /= 2;
}

return x % divisor;
}

/**
* Checks if a number is prime. Time Complexity: O(sqrt(n)). Works
* well with large numbers, but slower than Fermat's Little Theorem or
* other aproximations.
*
* @param number The number to check if it's a prime.
*
* @return TRUE if the number is prime, FALSE otherwise.
*
* @author  Andreas P. Koenzen
* @version 0.1
*/
bool is_prime_number(unsigned long long number) {
if (number <= 1) {
printf("Prime numbers start at 2!");
return false;
}

unsigned long long top = (unsigned long long) sqrt((double) number); // Only check if it's a prime 'til the square root of the number.
for (unsigned long long k = 2; k <= top; k++) {
if (number % k == 0) { return false; }
}

return true; // Return true if it's a prime!
}

/**
* Checks if a number is prime by aproximation using Fermat's Little Theorem.
*
* @see https://en.wikipedia.org/wiki/Fermat%27s_little_theorem
*
* @param number The number to check if it's a prime.
*
* @return TRUE if the number is prime, FALSE otherwise.
*
* @author  Andreas P. Koenzen
* @version 0.1
*/
bool is_prime_number_aproximation(unsigned long long number) {
bool debug = false;

srand((unsigned int)time(NULL));
for (int k = 0; k < 30; k++) {
unsigned long long a = rand() % (number - 2) + 2;
if (debug)
printf("\t\t> a is %llu\n", a);

if (modulo(a, (number - 1), number) != 1) {
return false;
}
}

return true;
}

/**
* This small app calculates all prime numbers between 2
* and N, given that N is any natural number > 2.
*
* @param number The top limit to check.
*
* @author  Andreas P. Koenzen
* @version 0.1
*/
void compute_primes(unsigned long long number) {
bool debug = false;
unsigned long long prime_counter = 1;
clock_t begin, end;
double time_spent;

// Check if N is > 2.
if (number <= 2) {
printf("\n");
printf("> Error: Number should be > 2!");
return;
}

begin = clock();
// Search for all prime numbers between 2 and k.
printf("\t> 2 is the *first* & *only even* prime!\n");
for (unsigned long long i = 3; i < number; i = i + 2) {
if (debug)
printf("\t> Looking number => %llu\n", i);

if (is_prime_number(i)) {
prime_counter++;

if (debug)
printf("\t> Found prime => %llu\n", i);
}
else {
if (debug)
printf("\t> Found composite => %llu\n", i);
}
}
end = clock();
time_spent = ((double) (end - begin)) / CLOCKS_PER_SEC;

printf("\n");
printf("> Found \"%llu\" primes between 2 and %llu\n", prime_counter, number);
printf("> Time Elapsed: %lf seconds\n", time_spent);
}