find prime numbers fast by Sieve of Eratosthenes method

please can anybody explain Sieve of Eratosthenes method for finding prime numbers fast in c

U can go through these 2 links…

  1. http://www.programminglogic.com/the-sieve-of-eratosthenes-implemented-in-c/

  2. http://www.geeksforgeeks.org/sieve-of-eratosthenes/

Hope it helps…:slight_smile:

1 Like

You can also find them in O(n) by computing the least prime divisor of each number.

const int N = 1<<27;
int lp[N+1];
vector<int> primes;
void sieve(){
  lp[0] = lp[1] = -1; 
  for(int i=2; i<=N; ++i)
    lp[i] = i;
  for(int i=2; i<=N; ++i)
    if(lp[i] == i)
      primes.push_back(i);
    for(int j=0; j<(int)primes.size() && primes[j]<=lp[i] && i*primes[j]<=N; ++j)
      lp[i*primes[j]] = primes[j];
  }
}
#define isprime(i) (i==lp[i])

So this both gives you a list of the primes in the vector primes, and a constant time check for a given prime which is #def’d.

2 Likes

You can go through the links mentioned by @kunal361 .

Here is the example how seive of eratosthenes works.

Lets say you want to find prime numbers in range [1,20]

Now first we will start with i=2

and cross all the number which are multiple of 2.

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

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

Now for i =3

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

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

Now for i=4

Hey do you need to check for value 4 ?, nope because 4 is already crossed , 4 is multiple of 2 and is there any possiblity that number is divisible by 4 not by 2 it’s not possible so no need to cross the multiples of i=4 .

Now for i=5

Here loop will break because 5*5 <= 20 is not True.

As 1 is not a prime number we will not consider it.

Now you can see that numbers left are 2,3,5,7,11,13,17,19 in range [1,20]

Hope this help .

Example Code:


    for(i=0;i<MAX;i++)
		prime[i]=1;
	for(i=2;i<MAX;i+=2)
		prime[i]=0;
	for(i=3;i*i<MAX;i+=2)
	{
        if(prime[i])
        {
            for(j=i*i;j<MAX;j+=i)
                prime[j]=0;
        }
	}
	j=0;
     prime[2]=1;
     // now all prime array elements having set value are prime number.
	for(i=2;i<MAX;i++)
	{
		if(prime[i])
			store_prime[j++]=i; // storing all prime numbers in an array(store_prime).
	}
    

Thanks.

One picture is better then 1000 words - http://en.wikipedia.org/wiki/File:Sieve_of_Eratosthenes_animation.gif

3 Likes

thanks all of you , it was very helpful