Hello,

I was stuck on the problem prime generation and searched for algorithm for segmented sieve and on TOPCODER Forum i found this process

Segmented sieve of Eratosthenes used to find primes in range [a, b] Steps 1- find all the primes up to sqrt(b), call them primes[] 2- create a boolean array is_prime[] with length = b-a+1 and fill it with true 3- for each p in primes set is_prime[i*p - a] = false starting at i=ceil(a/p) 4- for each is_prime*=true print i+a

Link: http://apps.topcoder.com/forums/?module=Thread&threadID=716232&start=0&mc=3

I tried implementing Segmented Sieve but i am unable to get the desired results.

Problem Link: http://www.spoj.com/problems/PRIME1/

My Code: http://ideone.com/mebiN5

I think that problem is in segmented sieve logic or may be i have committed a mistake, and i have a doubt too regarding the provided logic, i.e.

As mentioned **find all the primes up to sqrt(b), call them primes[]**

Suppose My input is

1 10

Then according to logic sqrt(b) will be 3… That means primes will be

[2,3]

But i think it is wrong…

About Error:

On Providing This input 1 ---> test cases 1 10 ---> [a, b] I am getting Output 1 4 5 6 7 8 9 10

And can you please explain where am i committing mistake…

Please…!!

Thank You…