Prime Sieve of Eratosthenes

From Algorithmist
(Redirected from Sieve of Eratosthenes)
Jump to: navigation, search

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 O\left({\frac  {N\log \log N}{\log N}}\right) 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 \log N bits for N.)

Algorithm[edit]

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.

Example[edit]

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 4,6,8\ldots - 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.

Pseudocode[edit]

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, PrimeArray(x) will be true if x>1 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.

Optimizations[edit]

  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 \leq {\sqrt  m}. (This is because if m=pq, then at least one of p and q must be \leq {\sqrt  m}.) 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^{2}, because if m<i^{2} 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^{2} 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 from 2 to N, do
  If isprime[i] is true,
    For each m from i^{2} to N, step i
      set is_prime[m] to false  ("cross it out")

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

Other optimizations[edit]

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

Implementations[edit]