You are not logged in. Please login at 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: it would be a great help.thanks in advance:)

asked 27 May '15, 00:16

rnagarjuna's gravatar image

accept rate: 0%

Check this link... @rnagarjuna

its quite easy to understand.


answered 27 May '15, 15:38

shivam9753's gravatar image

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

divyanshi26's gravatar image

accept rate: 0%

I understood the normal sieve,but this is little bit different and i found it from zobayers blog: 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.


answered 27 May '15, 10:44

shivam9753's gravatar image

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


answered 27 May '15, 15:00

binay_misra's gravatar image

accept rate: 5%

edited 27 May '15, 15:02

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 27 May '15, 00:16

question was seen: 1,658 times

last updated: 27 May '15, 15:38