Prime Numbers Generator

• Saturday, 23 Jan 2010
• code • generator • personal • tricks • it • fast • number • implementation • optimizations • curiosity • primes • cool
• 675 words

I believe I don’t have to describe what primes are, what are their properties and what not. This post is more a tribute to geek-ness of 2 friends-and-colleagues (@lucabox) that have fun thinking of algorithms to solve stupid (or less stupid), and always useless problems ;-) .

Optimus Prime :-P - yeah yeah, a stupid joke

Briefing

This code is based on the assumption that we want to generate very very large primes, so it uses unsigned long long to store the values, instead of classical unsigned int. Live with that.

Also, give that there is nothing much better then a “try-dividing-by-every-previous-prime” out there (there are alternatives, but I’m not aware of more complex ones), I took a look to some properties of Primes, and putted into the algorithm those properties as conditions for early stop:

1. Say P[i] are the previously calculated Primes; If trying dividing value V by every P[i] we find that P[i] > sqrt(V), stop dividing and classify V as a newly found prime
2. No need to check any even number: they are divisible by 2, so no primes by definition
3. No need to allocate more space then an array of the size of the requested prime ordinality: everything can be done in place

Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef unsigned long long ull;
typedef unsigned short int bool;

#define TRUE    1
#define FALSE   0

// Check if a number is a Prime, dividing it by all the other 
//  verified primes < of it's Square value.
bool is_prime(ull *primes, ull primes_found, ull value) {
    ull i;
    // Limit - Never check for primes larger then the sqrt(value)
    ull limit = (ull)sqrt(value);
    
    #ifdef DEBUG
        printf("Value: %llu - Primes found so far: %llu\n", value, primes_found);
    #endif
    
    for ( i = 0; i < primes_found; ++i ) {
        // Check if the value is divisible by this prime
        if ( value % primes[i] == 0 ) return FALSE;
        // Check if it's enough. Limit sqrt(value) exceded
        if ( primes[i] > limit ) break;
    }
    return TRUE;
}

ull* prime_numbers_generator(ull input) {
    ull* primes = NULL;
    ull primes_found = 1;
    ull i, j;
    
    // Allocating memory to store the Primes
    primes = (ull*)malloc(input * sizeof(ull));
    if ( NULL == primes ) return NULL;    
    
    // '2' is the first prime 
    primes[0] = 2;

    primes[1] = 3; // Let's start testing '3' for primality ;)
    for ( i = 1; i < input; ) {
        #ifdef DEBUG
            printf("i: %llu - Potential Prime: %llu\n", i, primes[i]);
        #endif
        // Check if 'primes[i]' is a prime
        if ( is_prime(primes, primes_found, primes[i]) ) {
            #ifdef DEBUG
                printf("Found a new Prime: %llu\n", primes[i]);
            #endif
            // Increment num of primes found so far
            ++primes_found;
            // Move to the next odd number
            primes[++i] = primes[i-1] + 2;
        } else {
            // Move to the next odd number, overriding the current one
            primes[i] += 2;
        }
    }
    
    return primes;
}

int main(int argc, char** argv) {
    ull input, i, *primes = NULL;
    if ( argc == 2 ) input = atoi(argv[1]); else return EXIT_FAILURE;
    
    // Calculate the required primes
    primes = prime_numbers_generator(input);
    if ( NULL == primes ) return EXIT_FAILURE;
    
    #ifndef FAST
    printf("All the first %llu Primes are:\n", input);
    for ( i = 0; i < input; ++i ) {
        printf("%llu ", primes[i]);
    }
    printf("\n\n");
    #endif
    
    printf("The Prime #%llu is %llu\n\n", input, primes[input-1]);
    
    return EXIT_SUCCESS;
}

Time Complexity of this algorithm is quite complex to calculate. Without condition 1. described above, we could quickly say that the complexity is an O(n²).

But I believe is more complex then that. Overall speaking, the complexity above is indeed correct, but it does vary a lot, because of the condition 1.: the number of times in which P[i] will be > sqrt(V) grows with the square value of P[i]. Means that the bigger the prime, the easier is to find the upper-bound of the modulo operations that will be actually executed. This could make the complexity also something like an Ω(n * log(n)). But this assertion is far from tested/demonstrated/verified, so I could be boldly wrong.