Help Regarding Segmented Sieve.

general
,
1

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[i]=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… :slight_smile:

1 Like
2

@rishabhprsd7

You have implemented your code wrongly.
And it’s very inefficient code even if you get correct output, I’m quite sure that you’ll get TLE for the given constraints.

Read about segmented sieve from here…

  • [Segmented sieve Bitwise optimized][1].

read and code it on your own!

Hope it helps :slight_smile:

Thank you!
[1]: http://zobayer.blogspot.in/2009/09/segmented-sieve.html

2 Likes
3

See this [explanation][1] to get better insight, and the following


[2]. The code is very much exactly the same way as the explanation says. The link mentioned above by @vicky002 is also good to understand.


  [1]: http://discuss.codechef.com/questions/54416/segmented-sieve?page=1#54462
  [2]: http://www.codechef.com/viewsolution/4807160
1 Like
4

Thank You @vicky002… :slight_smile:

5

Thank You @damn_me… :slight_smile:

6

Good Question indeed! I too was stuck in this one…Really helpful post and answers. :slight_smile:

1 Like