Tuesday, May 21, 2013

The Sieve of Eratosthenes This procedure, which dates back to the ancient Greeks, identifies all the primes less than a given number, in this case 121. It starts with the first prime — two, colored bright red — and eliminates all numbers divisible by two (colored dull red). Then it moves on to three (bright green) and eliminates all multiples of three (dull green). Four has already been eliminated, so next comes five (bright blue); the sieve eliminates all multiples of five (dull blue). It moves on to the next uncolored number, seven, and eliminates its multiples (dull yellow). The sieve would go on to 11 — the square root of 121 — but it can stop here, because all the non-primes bigger than 11 have already been filtered out. All the remaining numbers (colored purple) are primes. (Illustration:Sebastian Koppehel)