The Sieve of Eratosthenes
is an algorithm for finding prime numbers:
- List out the counting numbers starting at 2 (that is 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...)
- Mark the number 2 (circle it, underline it, etc - your choice)
- Cross off from your list all numbers that are multiples of the number just marked (multiples may already be crossed off - continue with the next multiple)
- Find the next uncrossed off number after the one just used in step 3; if there is no next uncrossed off number the go to step 7
- Mark this number
- Repeat from step 3
- Either extend the list of written out counting numbers (eg if the last number previously written was 100, then add 101, 102, 103, ..., etc to the list) and go back to step 2
- Or stop. All the marked numbers are the prime numbers less than or equal to the highest number that was listed.
The "Sieve" part of the name comes from the fact that all multiples of the number under consideration are crossed off or "sieved out" so that only the prime number remain.
The next number found in step 4 is the next larger prime to those found so far - it is the first number that is not a multiple of any the primes found so far and so must also be a prime.
For practical purposes, the list in step 1 will stop with some number and the algorithm will find all primes less than or equal to this number.