Anyone please explain segmented sieve of erathonesies??(if possible code too)
This link has your answer already. http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes
1 Like
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
4 Likes
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!!
3 Likes