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

×

cant understand sieve

any one please explain the sieve method provided in this link i was unable to understand what is the significance of base[] array,segment array:https://ideone.com/pH7b3X it would be a great help.thanks in advance:)

asked 27 May '15, 00:16

rnagarjuna's gravatar image

2★rnagarjuna
1519
accept rate: 0%


Check this link... @rnagarjuna

its quite easy to understand.

link

answered 27 May '15, 15:38

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

This seems like a code on generating prime numbers using the famous algorithm of Sieve of Eratosthenes which marks multiples of each prime number as composite (not prime) (Visit http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes for more). If you could provide the whole code, i.e., with the main function, and any other lines of code that are not here, we could help you in detail. :)

link

answered 27 May '15, 03:34

divyanshi26's gravatar image

1★divyanshi26
1
accept rate: 0%

I understood the normal sieve,but this is little bit different and i found it from zobayers blog:http://zobayer.blogspot.de/2009/09/segmented-sieve.html the above function is also generating primes using base array?but why MAX/64 in base[MAX/64].

(27 May '15, 08:38) rnagarjuna2★

@rnagarjuna.. You might have got confused by seeing that bulky bit shifts,You just need a simpler implementation of segmented sieve.Traditional sieve falis with limited time constraint..We need to fit the Sieve to our needs so that we run the Sieve only in that particular range.

Example. Suppose you need to find primes between a=141 and b=170.

You start by ((141)/2)==70 and then 70*2== 140.

you will mark 140,142,144,.....170.

Then 140/3==46 and 46*3== 138

mark 138,141,144,147.....168.

and then 141/5= 28 and 28*5=140

mark 140,145,150,155,160,165,170.

and so on..

one thing to notice is how are you getting these number? from where?(2,3,5,......)

You must first use simple sieve to form a list of primes up to sqrt(B).

So first try implementing this, without using bitshifts.. Once you successfully implement this, you would easily understand whats going there.

link

answered 27 May '15, 10:44

shivam9753's gravatar image

4★shivam9753
696112
accept rate: 17%

thank u shivam for the reply,but i know the above implementation and it is useful when finding the primes in a certain interval.But for this problem:http://www.spoj.com/problems/CPRIME/ it involves find the primes in more efficient way.The code in the zobayers blog is more efficient but i was unable to understand.

(27 May '15, 14:37) rnagarjuna2★

@rnagarjuna i can't tell about the code but i can provide a good link too the topic and i assume that sieve here means the sieve of Eratosthenes method for prime no, so the link which i would suggest is this one from mycodeschool ie this.

link

answered 27 May '15, 15:00

binay_misra's gravatar image

1★binay_misra
82216
accept rate: 5%

edited 27 May '15, 15:02

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:

×303

question asked: 27 May '15, 00:16

question was seen: 1,658 times

last updated: 27 May '15, 15:38