×

# Help Regarding Segmented Sieve.

 1 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 is1 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.. :) asked 22 Feb '15, 03:07 1.9k●1●12●42 accept rate: 14% 1 Good Question indeed! I too was stuck in this one..Really helpful post and answers. :-) (22 Feb '15, 20:55)

 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.. read and code it on your own! Hope it helps :) Thank you! answered 22 Feb '15, 06:44 256●1●3●14 accept rate: 27% Thank You @vicky002.. :) (22 Feb '15, 19:59)
 1 See this explanation to get better insight, and the following code. The code is very much exactly the same way as the explanation says. The link mentioned above by @vicky002 is also good to understand. answered 22 Feb '15, 09:07 3★damn_me 2.6k●2●13●36 accept rate: 24% Thank You @damn_me.. :) (22 Feb '15, 19:59)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×301
×13

question asked: 22 Feb '15, 03:07

question was seen: 2,665 times

last updated: 22 Feb '15, 20:55