Sieve of Eratosthenes

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Animation of the Sieve of Erazosthenes. It is the predecessor to the modern Sieve of Atkin, which is faster but more complex.

The Sieve of Eratosthenes is a simple test to check if a number is a prime number.

If someone wants to check for a certain number n to be prime, they do as follows:

  • Write numbers from 2 to that number onto a piece of paper.

Do the following:

  1. Get the next number that is not crossed out.
  2. Cross out all multiples of that number on your sheet.

Repeat this for all numbers until you reach the square root of n.

If n has been crossed out it is not prime.