2019 / Andreas Koenzen

Home

K-Zen
<< 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);
}