Sieve of Eratosthenes

Sieve of Eratosthenes

To generate prime numbers with the help of an algorithm given by the Greek mathematician name Eratosthenes, whose algorithm is known as "Sieve of Eratosthenes".

The Sieve of Eratosthenes is one of the most efficient way to find all the prime numbers smaller than n when n is smaller than 10,hundreds millions or so on.

Algorithm to find all the prime numbers less than or equal to a given number (integer) n by Eratosthenes method.

Algorithm

Step 1 : Create a list of consecutive integers from 2 to n(2,3,4,5........,n).

Step 2 : Initially, let p=2, the first prime number.

Step 3 : Starting from p^2, count up in increments of p and mark each of these numbers greater than or equal to p^2 itself in the list. These numbers will be p(p+1), p(p+2), p(p+3), and so on.

Step 4 : Find the first number greater than p in the list that is not marked. If there was no such number than stop. otherwise , let p now equal this number (which is the next prime), and repeat from step 3.

When the algorithm terminates, all the numbers in the list that are not marked are prime.

Example

Let us take an example when n=50, so we need to print all the prime numbers smaller than or equal to 50.

Step 1 : We create a list of all numbers from 2 to 50.

Step 2 : According to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it.

Step 3 : Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it.

Step 4 : We more to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it.

Step 5 : We continue this process and our final table will be this-

So the prime numbers are the unmarked one : -  

2,3,5,7,11,13,17,19,23,29,31,37,41,43,47.