Sieve of Eratosthenes

Eratosthenes (276-194 B.C.) was the third librarian of the famous library in Alexandria and an outstanding scholar all around. He is remembered by his measurement of the circumference of the Earth, estimates of the distances to the sun and the moon, and, in mathematics, for the invention of an algorithm for collecting prime numbers. The algorithm is known as the Sieve of Eratosthenes.

To find all prime numbers below a given number N, write all integers from 1 through N in order. One is a not a prime number and is crossed out right away. The algorithm proceed sequentially in steps. On every step, find the first number not yet crossed, mark it as prime and cross out all of its remaining multiples. Repeat this step while the least available number does not exceed the square root of N. This is so because, for a composite number A = a·b less or equal to N, the factors a and b can't both exceed N. Thus any prime factor of A can't exceed A, let alone N. When the algorithm stops, the prime numbers are either marked or not crossed.

In the applet below, pay attention to the button which at the outset labeled "2". At the beginning, this is the first not crossed number. When the button is clicked, a single step of the algorithm is performed. The number on the button is marked and its multiples are crossed out. The number is then replaced with the next available prime. At the end, the applet marks all the primes below the number specified by the spin control at the lower right corner of the applet.

A slight modification of the Sieve of Eratosthenes produces an unexpected result.

The Sieve of Eratosthenes appears also in disguise of a sequential process on a triangular grid.

References

1. J.H.Conway and R.K.Guy, The Book of Numbers, Springer-Verlag, NY, 1996.

Copyright © 1996-2007 Alexander Bogomolny