segmented_sieve

general
1

Hi, I have used sieve of eratosthenes a number of times, but am new to segmented version of it. I came to know about it while solving PRIME1. But I am stuck here. I first found primes up to some point (upto 100(say MAX) while testing, I will set it for 10^5). When the range of numbers is greater than MAX, the output is fine. But for less than it, I am not getting primes upto sqrt(Max_Number_in_range). I can’t understand how to modify the code. Please help.

P.S. Can you also tell me whether the approach is fast enough or I need some other modifications??

code : http://ideone.com/KdltlA

2

You are missing two things in your code:

for(long long j=i*i;j<MAX;j=j+i)
// the above line should be
for(long long j=2*i;j<MAX;j=j+i)

Secondly, in your result function consider this:

if(temp<low)
temp+=pri[i];
for(int j=temp-low;j<len;j+=pri[i])
if(j!=pri[i])
arr[j]=0;

when low is 1 and high is 10, pri[i] is 2 , then temp is 0 and then executes the line if(temp<low) due to which temp becomes 2.

Now j starts from temp-low which is (2-1) and is incremented by 2 in every step.
Thus arr[ele] =1 where ele is 1,3,5,7,9… . Thus it eliminates many of the prime numbers. So, just add one more condition :

if(temp==pri[i)
 temp+=pri[i];

For further, you can see my


[1] which is very similar to yours. 


  [1]: http://www.codechef.com/viewsolution/4807160
1 Like
3

Thanks a lot. I have now successfully completed the task. All I needed was

if(temp==pri[i)

temp+=pri[i];

Btw, the first mistake you pointed out is actually not a mistake. It can be

for(long long j=i*i;j<MAX;j=j+i)

instead of for(long long j=2*i;j<MAX;j=j+i).

And our codes are very similar.

4

Yeah, It can be this! I changed your code to something else for debugging and that required the change. Happy to help :slight_smile: