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…
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.
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
thanks all of you , it was very helpful