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 : KdltlA - Online C++ Compiler & Debugging Tool -

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:

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

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 :


For further, you can see my

[1] which is very similar to yours. 

1 Like

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



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.

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