Prime Sieve of Eratosthenes

From Algorithmist

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 O(N) space and time. (Note that N is the number. The size of the input would be the number of bits representing the number, which can be stored in logN bits for N.)

Contents 1 Algorithm 1.1 Example 1.2 Pseudocode 1.3 Optimizations 1.3.1 Other optimizations 2 Implementations

[edit] Algorithm

The Prime Sieve of Eratosthenes algorithm precalculates from the bottom up - given a table of N values, we "knock off" numbers that can't possibly be a prime - by counting up from hasn't been knocked off.

[edit] Example

Let N = 30:

 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.

[edit] Pseudocode

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 where i divides j, j from i + 1 to N
         set PrimeArray( j ) = false

At the end, PrimeArray(x) will be true if x is a prime number.

[edit] Optimizations

1. If m is a multiple of i and i is a multiple of p, then m is also a multiple of p. Thus, if i 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.
2. If a number m is not prime, then it has a factor that is . (This is because if m = pq, then at least one of p and q 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 m of i that are less than i², because if m < i² is composite, it would have already been crossed out by some number smaller than i.
3. By the above, as we will do nothing for i such that i² exceeds N, we can stop when that happens.

With these observations, we can write the following algorithm:

Start with an array is_prime[2..N], all initialized to true.
For each i such that  and , do
  If isprime[i] is true,
    For each multiple m of i such that , 
      "cross out m" — set is_prime[m] to false

This algorithm is usually what is meant when "the sieve of Eratosthenes" is mentioned.

[edit] Other optimizations

• 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.

[edit] Implementations

• Implementation in C
• Implementation in C++
• Sieve of Eratosthenes illustrated explanation. C++ and Java implementations.