Sieve of Eratosthenes

In mathematics, the Sieve of Eratosthenes (Greek: κόσκινον Ἐρατοσθένους) is one of the most important number of prime number sieves. It is a simple test for finding all the prime numbers up to any given number.

The way it works is to repeatedly cross out the composite numbers, which are the multiples of each prime. Starting from the multiples of 2, to the square root of that given number. Afterwards, the numbers left that are not crossed off are prime numbers.

With this method, the sieve of Eratosthenes can effectively find all of the smaller primes (below 10 million or so). The algorithm is named after Eratosthenes of Cyrene, a Greek mathematician. 

Example of how to do the sieve

1. 

   Prime Numbers - The Sieve of Eratosthenes

   List all the numbers from 1-???.
2. Cross out 1. It is a special number.
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. Keep going until every number has been either crossed out or circled and you basicly terrained all the numbers leaving just the prime numbers behind.

This only works up to a certain point. If you find out on larger numbers, you may eventally run out of space to write.

​References

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