Prime Sieve of Eratosthenes
The Sieve of Eratosthenes is an algorithm for generating a list of all prime numbers up to a given integer N. It does this using space and time. (Note that is the number. The size of the input would be the number of bits representing the number, which can be stored in bits for .)
The Prime Sieve of Eratosthenes algorithm precalculates from the bottom up - given a table of values, we "knock off" numbers that can't possibly be a prime - by counting up from hasn't been knocked off.
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
We know that 1 isn't a prime, so it's safe to cross it off. So we'll start at 2:
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
The smallest number that hasn't been processed is two, now let's knock out multiples of twos - by first going to - all you need is addition!
*2 3 5 7 9 11 13 15 17 19 21 23 25 27 29
Now that two is done, we can cross out multiples of threes - 6 is already crossed out, but 9 isn't, so we're going to cross that out, continuing..
*2 *3 5 7 11 13 17 19 23 25 29
And continuing on.
In its simplest form, without optimizations:
func sieve( var N ) var PrimeArray as array of size N initialize PrimeArray to all true for i from 2 to N for each j from i + i to N, step i set PrimeArray( j ) = false
At the end, will be true if is a prime number.
This is not the sieve of Eratosthenes though, because that algorithm sieves only by primes, as they are discovered, while this algorithm sieves by all natural numbers above 1. It is very easily parallelizable though.
- If is a multiple of and is a multiple of , then is also a multiple of . Thus, if has already been crossed out when the algorithm reaches it, we need not go crossing out its multiples, because they would have already been crossed out.
- If a number is not prime, then it has a factor that is . (This is because if , then at least one of and must be .) Thus, any number that is ever crossed out will be crossed out first by a number less than or equal to its square root. Putting this another way, we need not cross out multiples of that are less than , because if is composite, it would have already been crossed out by some number smaller than .
- By the above, as we will do nothing for such that exceeds , we can stop when that happens.
With these observations, we can write the following algorithm:
Start with an array is_prime, all initialized to true. For each from to , do If isprime is true, For each from to , step set is_prime to false ("cross it out")
This algorithm is usually what is meant when "the sieve of Eratosthenes" is mentioned.
- There is no need to store even numbers, as there is only one even prime number. (2, of course.)
- You can use bitmaps to pack the memory.
- If you are looking for only prime numbers you can generate them and keep adding them to a list.