# sieve of Eratosthenes

The sieve of Eratosthenes is the most efficient way to find all of the smallest prime
numbers. First described by Eratosthenes
of Cyrene, it involves making a list of all the integers less than or
equal to *n* (and greater than one), then striking out the multiples
of all primes less than or equal to the square root of *n*. The numbers
that are left are the primes. For example, to find all the primes less than
or equal to 30, we list the numbers from 2 to 30:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

The first number, 2, is prime, so we keep it out and strike out all of its multiples, leaving

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

The next number left, 3, is prime, so again we retain it and delete all of its multiples, leaving

2 3 5 7 11 13 17 19 23 25 29

Now we do the same thing for 5, another prime, to give

2 3 5 7 11 13 17 19 23 29

The next number, 7, is larger than the square root of 30, so all of the numbers left are primes.