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.


If you are reading this, your browser is not set to run Java applets. Try IE11 or Safari and declare the site https://www.cut-the-knot.org as trusted in the Java setup.

Sieve of Eratosthenes


What if applet does not run?

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.

As an aside, it may be easier to display all the composite numbers than going to the trouble of eliminating them step-by-step.

References

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

Related material
Read more...

Sieves

  • Listing All the Composite Numbers
  • Lucky Numbers
  • Sieve of Squares
  • The Parabolic Sieve of Prime Numbers
  • |Contact| |Front page| |Contents| |Algebra|

    Copyright © 1996-2018 Alexander Bogomolny

    71471884