Sieve of Eratosthenes

Sieve of Eratosthenes is one of the efficient method of finding the prime numbers in a given range.It is popularly known as Prime Sieve.The steps  involved are
1.create a range from 2 to any given range n.
2.let p be a variable initially equals to 2 (the first prime number)
3.Remove all the multiples of p
4.Now,p equals to the next number greater than p that is unmarked,If there was no such number, then you can stop.
5.Otherwise, p now equal this number (which is the next prime),
Example
 Lets find the prime numbers from 2 to 30

1.Create a list from 2 to 30

  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 31 
  32  33 34 35 36 37 38 39 40

 Initially p is 2 so,mark all the multiples of 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 31    
  32 33 34 35 36 37 38 39 40

   Now p is equal to the next unmarked number i.e., 3


Now mark all the multiples of 3

   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 31 
  32  33  34  35  36  37  38  39  40

Now p is equal to the next unmarked number , i.e., 5

Now  mark all the multiples of 5

   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 31 
  32  33  34  35  36  37  38  39  40

  The algorithm continues to find the next unmarked number and continues to mark all its multiples but it doesn’t  produce any change in the current list.

So  finally we obtained the prime numbers from 2 to 30 as

     2  3  5  7  11  13  17  19  23  29 31 37

Thus, it is as simple as that !!!!

Now lets look into the Implementation in C …..

#include "stdio.h"
#include "math.h"
int main(void) {
 // your code goes here
 int a[40],n=40,i,j;
 for(i=0;i< n;i++)
 a[i]=1;
 for(i=2;i< sqrt(n);i++)
 {
  if(a[i])
  for(j=i;i*j< n;j++)
  {
   a[i*j]=0;
  }
 }
 printf("primes from 2 to 40");
 for (i = 2;i< n; i++)
        if (a[i])
            printf("%d\n", i);
 
 return 0;
 

Output

primes from 2 to 40
2
3
5
7
11
13
17
19
23
29
31
37