Prime Numbers Wiki
Register
Advertisement

In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is a way to obtain a list of all the prime numbers up until a given point.

The method works by methodically crossing out the composite numbers. The user will cross out the multiples of each prime, from 2 and up until the square root of the final number. The numbers that are not crossed off are prime numbers.

The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician. 

How to Use the Sieve

Prime_Numbers_-_The_Sieve_of_Eratosthenes

Prime Numbers - The Sieve of Eratosthenes

  1. List all the numbers from 1 to a certain number.
  2. Cross out 1, since it is neither prime nor composite.
  3. Circle 2 and cross out every other multiple of 2.
  4. Circle 3 and cross out every other multiple of 3.
    Tip: Just add 6 to the first number, because all even numbers are crossed out.
  5. Circle 5 and cross out every other multiple of 5.
  6. Circle 7 and cross out every other multiple of 7.
  7. Circle the lowest number remaining after the previous step and cross out all its multiples.
  8. Repeat Step 7 until every number has either been crossed out or circled.

​References

  1. https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Advertisement