# Segmented sieve **URL:** \ **Category:** general\ **Tags:** segmentation, sieve\ **Created:** [October 30, 2014, 1:57am UTC](https://discuss.codechef.com/t/segmented-sieve/7862 "2014-10-30T01:57:30Z")\ **Posts on this page:** 10\ **Page:** 1
**Author:** ![nishanth9](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@nishanth9](https://discuss.codechef.com/u/nishanth9)\ **Post date:** [October 30, 2014, 1:57am UTC](https://discuss.codechef.com/t/segmented-sieve/7862/1 "2014-10-30T01:57:30Z")
Anyone please explain segmented sieve of erathonesies??(if possible code too) ---
**Author:** ![pranjalranjan](https://discuss.codechef.com/user_avatar/discuss.codechef.com/pranjalranjan/32/24644_2.png) [@pranjalranjan](https://discuss.codechef.com/u/pranjalranjan)\ **Post date:** [October 30, 2014, 2:02am UTC](https://discuss.codechef.com/t/segmented-sieve/7862/2 "2014-10-30T02:02:56Z")
This link has your answer already. [algorithm - Segmented Sieve of Eratosthenes? - Stack Overflow](http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes) ---
**Author:** ![topcoder\_7](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@topcoder\_7](https://discuss.codechef.com/u/topcoder_7)\ **Post date:** [October 30, 2014, 9:21am UTC](https://discuss.codechef.com/t/segmented-sieve/7862/3 "2014-10-30T09:21:55Z")
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 : [Sieve of Eratosthenes - Wikipedia](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) Reading stuff(with code) :- > **[Sieve of Eratosthenes - Codeforces](https://codeforces.com/blog/entry/3519)** > > Codeforces. Programming competitions and contests, programming community > **[Implementations of the Sieve of Eratosthenes](http://compoasso.free.fr/primelistweb/page/prime/eratosthene_en.php)** > > Explanations and optimized implementations of the Sieve of Eratosthenes in java, especially, a segmented version to avoid memory size limits My implementation : [Mm37uq - Online IDE & Debugging Tool - Ideone.com](http://ideone.com/Mm37uq) ---
**Author:** ![damn\_me](https://discuss.codechef.com/user_avatar/discuss.codechef.com/damn_me/32/208155_2.png) [@damn\_me](https://discuss.codechef.com/u/damn_me)\ **Post date:** [October 30, 2014, 10:08pm UTC](https://discuss.codechef.com/t/segmented-sieve/7862/4 "2014-10-30T22:08:39Z")
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!! ---
**Author:** ![rishabhprsd7](https://discuss.codechef.com/user_avatar/discuss.codechef.com/rishabhprsd7/32/109118_2.png) [@rishabhprsd7](https://discuss.codechef.com/u/rishabhprsd7)\ **Post date:** [October 30, 2014, 7:35am UTC](https://discuss.codechef.com/t/segmented-sieve/7862/5 "2014-10-30T07:35:51Z")
@pranjalranjan What actually do **Segmented Sieve** mean ? ---
**Author:** ![ganesh\_6](https://discuss.codechef.com/user_avatar/discuss.codechef.com/ganesh_6/32/24644_2.png) [@ganesh\_6](https://discuss.codechef.com/u/ganesh_6)\ **Post date:** [December 22, 2019, 5:04am UTC](https://discuss.codechef.com/t/segmented-sieve/7862/6 "2019-12-22T05:04:45Z")
Nice Explanation: [algorithm - Segmented Sieve of Eratosthenes? - Stack Overflow](https://stackoverflow.com/a/59441718/8706759) ---
**Author:** ![anon73162591](https://www.codechef.com/sites/all/themes/abessive/images/user_default_thumb.jpg) [@anon73162591](https://discuss.codechef.com/u/anon73162591)\ **Post date:** [December 22, 2019, 12:23pm UTC](https://discuss.codechef.com/t/segmented-sieve/7862/7 "2019-12-22T12:23:06Z")
There’s a question on SPOJ i guess which is related to this topic ---
**Author:** ![joyoshish](https://discuss.codechef.com/user_avatar/discuss.codechef.com/joyoshish/32/3653_2.png) [@joyoshish](https://discuss.codechef.com/u/joyoshish)\ **Post date:** [March 16, 2020, 6:12pm UTC](https://discuss.codechef.com/t/segmented-sieve/7862/8 "2020-03-16T18:12:22Z")
It helped. Thank you. ---
**Author:** ![manas321](https://discuss.codechef.com/user_avatar/discuss.codechef.com/manas321/32/14492_2.png) [@manas321](https://discuss.codechef.com/u/manas321)\ **Post date:** [April 21, 2020, 1:23pm UTC](https://discuss.codechef.com/t/segmented-sieve/7862/9 "2020-04-21T13:23:25Z")
Great explanation must read this to understand the concept of segmented sieve ---
**Author:** ![saurabhshadow](https://discuss.codechef.com/user_avatar/discuss.codechef.com/saurabhshadow/32/347886_2.png) [@saurabhshadow](https://discuss.codechef.com/u/saurabhshadow)\ **Post date:** [April 21, 2020, 1:34pm UTC](https://discuss.codechef.com/t/segmented-sieve/7862/10 "2020-04-21T13:34:11Z")
I found this more [**explaining**](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) …Have a look if still, it’s not clear.