×

# cant understand sieve

 0 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 15●1●9 accept rate: 0%

 0 its quite easy to understand. answered 27 May '15, 15:38 696●1●12 accept rate: 17%
 0 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. :) answered 27 May '15, 03:34 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)
 0 @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. answered 27 May '15, 10:44 696●1●12 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)
 0 @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. answered 27 May '15, 15:00 82●2●16 accept rate: 5%
 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:

×303

question asked: 27 May '15, 00:16

question was seen: 1,658 times

last updated: 27 May '15, 15:38