Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

sieve of Eratosthenes





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.


Related category

   • PRIME NUMBERS