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[i]=true print i+a
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
Then according to logic sqrt(b) will be 3… That means primes will be
But i think it is wrong…
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…