Prime Number Generators

Every few years, I’d hear news of someone finding a prime number and getting awarded big bucks for doing so. Whenever I heard this kinda news, I’d think about how easy it would be to actually find them myself. I mean, it almost seemed too easy:

      1) Remove all even numbers
      2) Remove all multiples of 5
      3) Check all numbers ending in 3, 7, and 9 if they're prime or not.

So if you have a set of n numbers, taking out all the even numbers would leave you with n/2 numbers. Unfortunately, taking out the multiples of 5 didn’t do much, so its actually leaving you with 2n/5 numbers. My algorithm back in the day had also left out one important fact: How do I actually check if they’re prime?

With project euler, I was forced to actually re-evaluate my algorithm, and you know what? It failed spectacularly! However, it led me to something else. Its this SWEET algorithm called the “Sieve of Eratosthenes”.  Here’s how it goes:

     1) Make a list A of all numbers 1 to n.
     2) Make a list B to hold all the primes you find. The first item will be 2.
     3) Remove ALL multiples of 2 from list A.
     4) The first remaining number will be a prime. Add this to B.
     5) Grab that number and remove all multiples of it from list A.
     6) Repeat 4) and 5) until no numbers are left in List A.

It works perfectly (albiet pretty slow)  and it does its job: getting a list of n primes.  Apparently other people thought so themselves, so much in fact, that they actually wrote a poem about it!

Sift the Two’s and sift the Three’s,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.

Isn’t that cool? It even rhymes!

When I was learning “Computer and Network Security”, I actually learnt about another prime number generator. It uses a few complicated theories, namly Fermat’s little theorem and the Fermat primality test (aww man, I could of used this in my first algorithm!). Its good and it works, but its not as cool as the Sieve.

In other news, I can’t believe I just blogged about prime numbers. I am living up to my blog’s tagline already!