cant understand sieve

any one please explain the sieve method provided in this link i was unable to understand what is the significance of base[] array,segment array:https://ideone.com/pH7b3X
it would be a great help.thanks in advance:)

This seems like a code on generating prime numbers using the famous algorithm of Sieve of Eratosthenes which marks multiples of each prime number as composite (not prime) (Visit http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for more).
If you could provide the whole code, i.e., with the main function, and any other lines of code that are not here, we could help you in detail. :slight_smile:

I understood the normal sieve,but this is little bit different and i found it from zobayers blog:http://zobayer.blogspot.de/2009/09/segmented-sieve.html
the above function is also generating primes using base array?but why MAX/64 in base[MAX/64].

@rnagarjuna
You might have got confused by seeing that bulky bit shifts,You just need a simpler implementation of segmented sieve.Traditional sieve falis with limited time constraint…We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.

Example.
Suppose you need to find primes between a=141 and b=170.

You start by ((141)/2)==70 and then 70*2== 140.

you will mark 140,142,144,…170.

Then 140/3==46 and 46*3== 138

mark 138,141,144,147…168.

and then 141/5= 28 and 28*5=140

mark 140,145,150,155,160,165,170.

and so on…

one thing to notice is how are you getting these number? from where?(2,3,5,…)

You must first use simple sieve to form a list of primes up to sqrt(B).

So first try implementing this, without using bitshifts…
Once you successfully implement this, you would easily understand whats going there.

thank u shivam for the reply,but i know the above implementation and it is useful when finding the primes in a certain interval.But for this problem:http://www.spoj.com/problems/CPRIME/ it involves find the primes in more efficient way.The code in the zobayers blog is more efficient but i was unable to understand.

@rnagarjuna i can’t tell about the code but i can provide a good link too the topic and i assume that sieve here means the sieve of Eratosthenes method for prime no, so the link which i would suggest is this one from [mycodeschool]
1 ie this.

Check this link
@rnagarjuna

its quite easy to understand.

//