The Sieve of Eratosthenes is a prime-finding algorithm developed by the ancient Greek mathematician Eratosthenes. It works by writing down as many numbers as needed and then, traversing from lowest to highest, cross out all multiples of a number, beginning with 2. The numbers that remain are considered prime and the lowest of it will be used for the next run.
The Sieve of Eratosthenes refers to a specific algorithm to find primes, invented by the Greek "mathematician, geographer, poet, astronomer, and music theorist" Eratosthenes of Cyrene.
It works relatively simply. All numbers that will be analyzed are written down; then, beginning with the lowest number, all multiples of it are crossed out. Then the next free number is used to do the same. When finished, the remaining numbers can be considered prime:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 ,27, 28, 29, 30,
1 will be excluded, thus the first number to use is 2. Upon crossing out all multiples of 2, one arrives at following sieve:
x, 2, 3, x, 5, x, 7, x, 9, x, 11, x, 13, x, 15, x, 17, x, 19, x, 21, x, 23, x, 25, x, 27, x, 29, x,
The next available number is 3. Upon crossing out all multiples of 3, one arrives at:
x, 2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, x, 17, x, 19, x, x, x, 23, x, 25, x, x, x, 29, x,
The next available number is 5:
x, 2, 3, x, 5, x, 7, x, x, x, 11, x, 13, x, x, x, 17, x, 19, x, x, x, 23, x, x, x, x, x, 29, x,
This procedure can be repeated up to a certain threshold, where no more numbers are crossed out in the available numbers. This threshold is defined by the square root of the highest number analyzed. This is commonly also referred to as the "Optimized Sieve of Eratosthenes".
Implementation notes
The Sieve of Eratosthenes does not involve any division or modulo operations. Any prime-finding algorithm that involves division is not the Sieve of Eratosthenes.
The Sieve of Eratosthenes is an efficient method of finding all the primes below a certain number. If you want to test the primality of just one number, it may be faster to use a different algorithm.
To find the first n primes, you would need to estimate the size of the sieve first. It may be useful to know that the nth prime will be no larger than n ln n + n ln ln n, for n ≥ 6.
