What is the sieve of eratosthenes?

It is a method for finding the prime and composite numbers

Here is an example of the sieve. Firstly the definition of a prime is a number divisible only by itself and one. From that we can build this sieve, it can of course go on as far as you wish. Though with very large numbers it becomes impractical.

1 2 3 4 5 6 7 89 10 11 12 13 1415 16 17 18 19 20 2122 23 24 25 26 27

Then starting at 1 we highlight all those numbers which can be divided by numbers lower than themselves. Each number in bold is not a Prime number because a number below it can be divided into it with no remainder. Each number in italics is a prime, because, as we have said it can only be divided by 1 and itself. It should also be noted that 2 is the only even prime number, all other even numbers can be divided by 2. So if you are asked if a number is prime and it is an even number then you do not have to check because it is not.

The Sieve of Eratosthenes is a way of determining which numbers are prime.

• Zero and one are, by definition, not prime.
• Write a list of numbers from two up to the highest number in which you are interested.
• The first number, 2, is prime and every multiple of it can not be prime, so cross them out -- that is 4, 6, 8, 10, and so on
• The next number not crossed out will be 3. That is prime but its multiples can't be, so cross them out -- 6, 9, 12, 15, and so on.
• 4 is crossed out, so the next number not crossed out is 5. That is prime, so cross out its multiples, 10, 15, 20, and so on.
• Continue this process until you can not cross out any more numbers (about halfway down the list)
• When you have finished, all numbers not crossed out are prime.