Sieve of Erathosthenes.

Sieve of Eratosthenes is a simple algorithm to find prime numbers. Sieve of Eratosthenes is a great example of the sieve approach. This post is A way to find out prime numbers lesser than a very big number !!

Screenshots/Sample Output:

Code for It:

#include<stdio.h>
int isprime[10000001]={0};
main()
{ long long int i,j;
 isprime[0]=1;
 isprime[1]=1;
 for(i=2;i*i<10000001;i++)
 { if(isprime[i]==1)
  { continue;
  }
  for(j=i*2;j<10000001;j+=i)
  { isprime[j]=1;
  }
 }
 printf("enter the no. till which the small primes are to be found : ");
 scanf("%lld",&j);
 printf("the prime numbers till %lld are: \n",j);
 for(i=2;i<=j;i++)
 { if(isprime[i]==0)
  printf("%lld\t",i);
 }
}

Efficiency of the code :

The normal algorithm we follow has its complexity defined by O(n).

This Sieve algorithm reduces it to O(n*loglog(n))/O(1).