The Sieve of Eratosthenes

Yesterday, I reviewed The Music of the Primes: Searching to Solve the Greatest Mystery in Mathematics, a book by Marcus du Sautoy.

In the book, du Sautoy explains the Sieve of Eratosthenes, an algorithm for finding all the prime numbers under a given limit.  The concept is surprisingly simple – for a set of numbers less than N, begin with the first prime number (2) and throw out all of its multiples (4, 6, 8, etc) up to N.  Then start over with the next number remaining (3) and throw out all of its multiples up to N.  Some multiples of 3, such as 6 and 12, will have been thrown out in the prior step.  Keep repeating the process until there are no numbers less than N left to be thrown out.

Continue reading