×

# Segmented sieve

 0 Anyone please explain segmented sieve of erathonesies??(if possible code too) asked 30 Oct '14, 01:57 16●2●5 accept rate: 0%

 6 Segmented - consisting of or divided into segments, Sieve - A tool(here:algorithm) to separate numbers of one characteristic (here:prime) from numbers of another(here:natural numbers). Sieve of Eratosthenes : http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes Reading stuff(with code) :- http://codeforces.com/blog/entry/3519 http://compoasso.free.fr/primelistweb/page/prime/eratosthene_en.php My implementation : http://ideone.com/Mm37uq answered 30 Oct '14, 09:21 2.9k●31●53 accept rate: 9%
 3 It means, that we are making segmented with the sieve we have. I once saved this text for future: "Say i need to find the prime numbers between 125 and 140 .One way is to find all primes till 140 using traditional sieves and then find how many of them are greater than 125.This will not work within limited time constraints.We need to fit the Sieve to our needs so that we run the Sieve only in that particular range. The first prime is 2.We divide the starting number x=125 by 2 .We round off to smaller integer we get 62.We again multiply by 2 we get 124.What is 124 ?it is the first smaller number than x that is divisible by the prime 2.We start from 124,increment by 2 in each step and remove all elements between 125 and 140.That is we remove 126,128,130,132,134,136,138,140.What we did was that we did the first step in traditional sieve but just offset the starting elements to the closest composite number less than the starting point of the range.Next we do this with the 2nd smallest prime number 3.125/3=41.41*3=123.We start from 123 go till 140 (inclusive) in steps of 3 and cut the numbers 126,129,132,135,138.Next we do with 5.But from where do we get the prime numbers 2,3,5 and so on and how long do we need to do that? That can be done well by generating the sieve upto 10^6 which can be easily done". Hope it clears!! answered 30 Oct '14, 22:08 3★damn_me 2.6k●2●13●36 accept rate: 24%
 0 This link has your answer already. http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes answered 30 Oct '14, 02:02 2.0k●2●14●32 accept rate: 20% @pranjalranjan What actually do Segmented Sieve mean ? (30 Oct '14, 07:35)
 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: 30 Oct '14, 01:57

question was seen: 8,547 times

last updated: 30 Oct '14, 22:08