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
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

More >