[Algorithm] - Sieve algorithm to find prime numbers, with an example

This algorithm generates prime number in the range of '0' to 'a given input number'

This post will tell you in detail about "Sieve algorithm with an example"

Algorithm:

Detailed Explanation: 

Consider the input to be 15. I.e., n=15. That is we have to generate prime numbers between 0 to n.

1. The first ‘for loop‘ iterates for p=2 upto n. Each time making A[p]=p. So after this for loop, the array must contain the values from 2 to n. [1 is not included since it never can be a prime number].

Then the value of array A must be now

   A={2,3,4,5,6,7,8,9,10,11,12,13,14,15}

2. The second for loop is the main logic in this algorithm.

• Rather than explaining the logic, let me explain with the example. So that you yourself can understand the logic. 
• This loop runs from ‘2’ to value less than Square root of 15. That is, loop will run for values 2 and 3 (Obvious).
• Now inside the loop check whether A[p] not equal to 0. At the beginning, p=2 and A[2] is not equal to 0, because A[2]=2. (From the first step).
• So value of j is assigned to 2*2 that is 4. And inside the while loop, all the values which are multiple of 2 are set to zero except the number 2 [Indicating that the multiples are no’t prime numbers]. This is done by making A[j] = 0 ( j ranging from 4 to 14, when j becomes 16, while loop terminates). 
• Now at this point, all the multiples of 2 except the number 2 are removed from the array and made to zero. 

The array after this iteration is 

A={2,3,0,5,0,7,0,9,0,11,0,13,0,15}  

Multiples of 2 are removed

3. Next step is to make the multiples of 3 to ‘Zero’ except the number 3, since it is prime.

• For next iteration of for loop, p=3 and j starts from 6 to 15. Making the value A[j]=0 at each j values. Loop terminates when j becomes 18. After this iteration, Array contains

A={2,3,0,5,0,7,0,0,0,11,0,13,0,0}    

Multiples of 3 are removed

4. Now p=4, which becomes false condition for the first ‘for loop’ and we now contain the array A,with prime numbers and '0's. We now need to transfer the elements which are not zero, to a new array ‘L’. That is done in third for loop. (Which is Self explanatory).

Now at last, return L, which contains the prime numbers. 

So L={2,3,5,7,11,13}, the required prime numbers.

I think this problem can answer the question "Explain sieve algorithm" or "What is sieve algorithm" of VTU Students. :P

Author : Anonymous

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!

Sharing is sexy!

Related Articles