You are not logged in. Please login at www.codechef.com to post your questions!

×

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 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.. :)

asked 22 Feb '15, 03:07

rishabhprsd7's gravatar image

2★rishabhprsd7
1.9k11242
accept rate: 14%

edited 22 Feb '15, 03:11

1

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

(22 Feb '15, 20:55) ansh1star0333★

@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!

link

answered 22 Feb '15, 06:44

vicky002's gravatar image

1★vicky002 ♦♦
2561314
accept rate: 27%

Thank You @vicky002.. :)

(22 Feb '15, 19:59) rishabhprsd72★

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.

link

answered 22 Feb '15, 09:07

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

Thank You @damn_me.. :)

(22 Feb '15, 19:59) rishabhprsd72★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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