Sieve of Eratosthenes

TarifEzaz

About 2300 years ago from today, famous Greek mathematician Euclid proved that there are an infinite number of prime numbers. Since then people have been searching for these prime numbers. In 1849, one of the greatest mathematician of all time, Carl Fredrick Gauss, had identified almost all of the prime numbers within the first 3 hundred thousand whole numbers.

In the age of computers, we can find large prime numbers in the blink of an eye. But to do that, we need to know a bit of programming and a 2000 year old algorithm.

By the end of this tutorial, you will be able to figure out a solution on your own to Gauss's problem.

What is a Prime Number?

A prime number is an integer number that is divisible by 1 and the number itself only. For example, 7 is divisible by 1 and 7 only. But 6 is not a prime number because 6 is be divisible by 2 and 3 as well. It is worth mentioning that 1 itself is not a prime number.

Now if you are asked to determine if a number is a prime number, you can do so by checking if the number is divisible by any number other than 1 and itself.

If you are given the number 25, you can check it as follows:

Dividing 25 by 2 yields a remainder of 1, so 25 is not divisible by 2. Therefore 25 may still be a prime number.

Dividing 25 by 3 yields a remainder of 1, so 25 is not divisible by 3. Therefore 25 may still be a prime number.

Next, dividing 25 by 4 yields a remainder of 1, so it may still be a prime number.

But, 25 can be divided by 5 without any remainder, and so it is clear that 25 is anything but a prime number.

To put it simply, if you are given a number N, and you check its divisibility by every number from 2 to N-1 and find that it is not divisible by those numbers, then you can be certain that N is a prime number.

Here is a bit of pseudo code to test if a number n is prime.

function isPrime(n)
  for i = 2 to n-1 (inclusive)
    if (n % i) == 0
      return false
  return true

You can now solve this problem: Is Prime. Give it a go!

Now there is a problem with this approach. Suppose you want to determine if 71 is a prime number. To follow the approach outlined above, you will need to check divisibility of 71 by 69 numbers to determine if it is a prime number. But, is it really necessary to check against so many numbers? Think about it: if the number had 6 digits, you would have to check it against so many numbers. There should definitely be a better way to determine if a number is prime.

If you think a bit, you will observe that a number N cannot be divided without remainder with any number greater than N/2. To determine if 71 is prime, you need to check its divisibility with numbers only up to 30.

But is there a more efficient way?

Magic of Square Roots

Let's assume that a is a whole number that divides N without any remainder. In that case N/a should also be a whole number. Let's assume that the other number is b. And, let's assume that the square root of N is c. Now, for any positive whole number N, only one of the following is true:

• a is greater than c, and b is lesser than c.
• b is greater than c, and a is lesser than c.
• a and b are both equal to c.

The reasoning behind this claim is rather interesting. I will leave it for you as a thought exercise along with this hint: c times c is N.

Now that we know this, to determine if N is a prime number, we just need to check its divisibility with numbers 2 to sqrt(N). This is because, if N is not a prime number, then there should at least be a divisor of N between 2 and sqrt(N) (inclusive).

function isPrime(n)
  let c = √N
  for i = 2 to c (inclusive)
    if (n % i) == 0
      return false
  return true

This is a much more efficient approach now. If we now want to determine if a number below 1000000 is prime, we just need to check it against at most 1000 numbers.

Sieve of Eratosthenes

If you were asked to find all of the prime numbers between 1 and 100, how would you do that?

You could apply the approach described above to achieve this goal. Take each number between 1 and 100 and check if it is a prime number using the approach described above.

That means if you want to determine the primility of numbers between 1 and N, you will have to run a loop from 1 to N with another loop within it that will determine the primility of each number. For a number X, the inner loop will run for sqrt(X) iterations.

Although this is correct, there is an even more efficient approach. Greek Mathematician Eratosthenes described this technique sometime during 200 B.C.

Let's see how this technique could work on paper. If you had to determine the primility of numbers between 1 and 20, you would need to draw 20 boxes. All of the boxes are empty and they each represent a number from 1 to 20: the first box is 1, the second box is 2, the third box is 3, and so on.

  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

We know that 1 is not a prime number. Therefore we will but an X in the first box.

  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
[X] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Next we will move on to the second box. The second box represents 2 and it is empty. We will soon understand what it means to have an empty box. Right now we will put an X in every box representing a number greater than 2 and a multiple of it: 4, 6, 8, etc.

  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
[X] [ ] [ ] [X] [ ] [X] [ ] [X] [ ] [X] [ ] [X] [ ] [X] [ ] [X] [ ] [X] [ ] [X]

The next empty box represents 3. This time we will put an X in every box representing a number greater than 3 and a multiple of it: 9, and 15.

  1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
[X] [ ] [ ] [X] [ ] [X] [ ] [X] [X] [X] [ ] [X] [ ] [X] [X] [X] [ ] [X] [ ] [X]

The next box represents 4 but it already has an X in it. We will now move to the fifth box. Following the same steps we would put an X in every box representing a number greater than 5 and a multiple of it, but interestingly, these boxes already have X's in them: 10, 15, and 20.

Now let's take a look at the boxes that do not have an X in them. These boxes represent the numbers 2, 3, 5, 7, 11, 13, 17 and 19. Do these numbers look familiar? Yes, they are the prime numbers up to 20.

With this technique, we can find the prime numbers from 1 to N much more efficiently. The name of this technique is Sieve of Eratosthenes.

The technique is easy to do work with manually when the range is small. For a bigger range, you can always write a program to do the same.

Here is the pseudo code for Sieve of Eratosthenes:

function sieve(n)
  let primes = array of length n initialized with true
  primes[1] = false
  for h = 2 to n
    if primes[h]
      for x = multiples of h up to n (i.e. 2*h, 3*h, 4*h, ....)
        primes[x] = false

You can now solve this problem: Correct the Sieve. Give it a go!

Related Problems

• N'th Prime
• VECTAR8 - Primal Fear on SPOJ
• NFACTOR - N-Factorful on SPOJ
• Noldbach problem on Codeforces