Sieve of Eratosthenes

In mathematics, the Sieve of Eratosthenes is a simple, ancient algorithm for finding all prime numbers up to a specified integer^[1]. It works efficiently for the smaller primes (below 10 million) ^[2]. It was created by Eratosthenes, an ancient Greek mathematician. When the Sieve of Eratosthenes is used in computer programming, wheel factorization is often applied before the sieve to increase the speed.

The algorithm

1. Create a contiguous list of numbers from two to some highest number n.
2. Strike out from the list all multiples of two (4, 6, 8 etc.).
3. The list's next number that has not been struck out is a prime number.
4. Strike out from the list all multiples of the number you identified in the previous step.
5. Repeat steps 3 and 4 until you reach a number that is greater than the square root of n (the highest number in the list).
6. All the remaining numbers in the list are prime.