# Prime Numbers Generator

• 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 = 2;

primes = 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); 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(n2).

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.