 # 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…

Hope it helps… 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 = lp = -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]

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=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.

thanks all of you , it was very helpful

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

3 Likes