The Sieve of Eratosthenes

I recently read Prime Obsession by John Derbyshire; a book all about prime numbers and one of the worlds greatest Mathematicians: Bernhard Riemann. The books main focus is on the Riemann Hypothesis which states that:

The real part of any non-trivial zero of the Riemann zeta function is 1/2.

I’d love to say that after reading the book I understand the Maths behind it but alas I do not. That’s not surprising though as it’s a problem that has yet to be solved, 159 years after Riemann paper on “On the Number of Primes Less Than a Given Magnitude”. It doesn’t look like it’s going to be solved any time soon either! If you’re interested it’s one of the Clay Mathematics Institutes Millennium Prize Problems in which you can earn yourself US$1,000,000.

While reading Prime Obsession it mentioned an interesting method for finding prime numbers called “Sieve of Eratosthenes” (pronounced air-a-TAWS-the-nEEss). Eratosthenes was a librarian at the great library of Alexandria around 230 B.C.E. It’s quite obvious how the method works once you know it, and easy to see why it’s called a sieve. The method goes like this:

1. Write a list of numbers in which you wish to identify the primes, say 2 – 100 (exclude 1 as it isn’t required)
2. Take the first number 2. Leaving 2 intact, remove every second number.
3. Move onto the next number 3. Leave 3 intact and remove every third number
4. Take the next number 5. Leave 5 intact and take away every fifth number
5. Repeat until you get to the end of your list

The end result is the set of prime numbers up to your given number. Essentially all you are doing is removing any number that is divisible by the 1st, 2nd… Nth number. Clever stuff!

As a little side project I decided to implement this method using JavaScript, displaying the result in the browser. You can view the demo here. For fun I created two implementations, one relying heavily on the DOM, the other only using arrays. As you’d expect the DOM method is slow; looping through large tables multiple times doesn’t make for a quick execution time. The second method using a single JavaScript array is much quicker. I’ve added a stats panel to the right hand side of the page so it’s possible to compare results from both methods over different input values.

I’ve added a limit to the number you can enter into the input box (5000), I don’t want anyone blaming me for crashing their browser by entering 10 million! :) Feel free to copy the demo if you want to see what happens at higher values.

Thanks goes to John Resig for his very handy Array Remove method. It made removing non-primes from the numbers array very simple indeed.

Prime Obsession is a superb book but a word of warning, it contains a lot of higher level Mathematics, so may not be to everyone’s taste. It certainly made my brain hurt at times; not always what you need on that 8am commute to work! View the demo.