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

×

Segmented sieve

Anyone please explain segmented sieve of erathonesies??(if possible code too)

asked 30 Oct '14, 01:57

nishanth9's gravatar image

2★nishanth9
1625
accept rate: 0%


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

link

answered 30 Oct '14, 09:21

topcoder_7's gravatar image

2★topcoder_7
2.9k3153
accept rate: 9%

edited 30 Oct '14, 11:47

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

link

answered 30 Oct '14, 22:08

damn_me's gravatar image

3★damn_me
2.6k21336
accept rate: 24%

link

answered 30 Oct '14, 02:02

pranjalranjan's gravatar image

4★pranjalranjan
2.0k21432
accept rate: 20%

@pranjalranjan
What actually do Segmented Sieve mean ?

(30 Oct '14, 07:35) 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: 30 Oct '14, 01:57

question was seen: 8,547 times

last updated: 30 Oct '14, 22:08