Segmented Sieve | Sample Video II for Essential Maths for CP | GeeksforGeeks

[@shashankpathak63]

One of the best explanation on Segmented sieve .

[@GeeksforGeeksVideos]

Thank you Shashank !

[@johndixit57]

@@GeeksforGeeksVideos best explanation

[@human75788]

With that level of explanation I solved it myself within 10 minutes. Seems like it was too easy. Awesome Sir❤

[@PriyaSingh-jr6fl]

This is literally the best explanation video of gfg till now.

[@cwmayank]

Simple and perfect video. Thank u, sir. GFG has made my life easy.

[@gouravkhator]

It's the best explanation I can get for segmented sieve. Thank you so much sir for this video

[@sapnilpatel1645]

The Best explanation about segmented sieve. Thank you so much sir 🙂.

[@sritanuchakraborty4678]

Great video, few things I've noticed and would like to point it out. Please correct me if I am wrong or the step is redundant: 1. For l=1, h=any number, you need to handle isPrime[l] separately. 2. We are calculating the sieve from 1 to sqrt(h)+1. If a subset of this sieve set has some elements common with the range[l,h], then the prime numbers will also be marked as false. For e.g. l=1 & h=100. n=10. prime={2,3,5,7}. While calculating sm, it will start from 2 and will mark that as false. So a condition such as if(m!=p) is necessary in order to not mark those primes as false. 3. Not really necessary, but another way to compute sm can be sm = ((l+p-1)/p)*p. You don't need the next if statement afterward. 4. A question, say l=2000, h=1e9, the isPrime vector in the segsieve function will be initialized with 99,99,98,000 elements as false. Can someone please point out where is the improvement (both in space & time) for such a huge range over a normal sieve? A naive solution could be to divide up the range into partitions, say it holds 1e7 elements(a bool vector with 1e7 elements is doable), loop over range/1e7 times and each time get the primes with updated low and high for the current range and push them back into a vector. But are there any other optimized solutions?

[@dakshkalucha5408]

Thanks, point 2 really helped a lot

[@anuraggulati2167]

this video clears all the doubts..thankyou sir🙂🙂😇🥰

[@leepakshiyadav1643]

Amazing explaination 👏👏

[@sanketkhore9400]

The code is wrong... In segmented we are suppose to find the primes by dividing the range in segments but in your program you are not dividing it in segments. Infact, in segmented_sieve function you are doing the same thing as that of simple sieve(If L=0 and H=100 then also you are making an array of(H-L+1) which is equal to H+1 in this case). So it is not solving the space complexity problem.

[@UpendraKumar-mu7mk]

Sir, I have a test case when this code will not give desired result. Whenever l=1, sm=(l/p)*p for a prime p , will be p. So it will mark isprime[p]=false, which it should'nt.

[@mralgorithms5127]

when l=1 1/p = 0 as the least prime number is 2 and this an integer division (0*p)=0 so isprime[0]=false which is true as 0 is not a prime number

[@vaibhavjaiswal7811]

Yes you are right. I got an error with the code given by sir. I just added if(m!=p) before changing value to false, and it worked. Also you need to ignore 1 in output which is pretty easy ig.

[@tanishqmahendrasaini3764]

@@vaibhavjaiswal7811 Thanks I got stuck here.

[@PrinceKumar-el7ob]

@@vaibhavjaiswal7811 thanks bro !! case of 1 has to handled too!!

[@chinmaydeshpande8969]

Best explanation Sir thank you!

[@OlliS71]

A segmented sieve is only slightly faster than a non-segemented sieve since you have only one comparison of the found prime against the root of the range. That's one jump in assembly that is almost always predicted correctly.

[@codingmaster008]

thanks sandeep sir for the awesome explaination👍

[@ShivamVerma-rr6nb]

In void sieve function it should be long long j=2*i ; j

[@murtuza_shahzad]

I was also wondering the same thing.

[@anmol3]

Both are correct

[@1onlyArunzz]

j=i*i better optimisation ;

[@shivamkumarsingh667]

Best Explanation 🙌

[@HappyHappy-ih5zp]

Ek baar mein samjh aa gya Thanks Sir.

[@ParthArora-s2i]

sir in void sieve in the for loop j++ should be replaced by j += i; please correct me @GeeksforGeeksVideos

[@MrMadcatsam]

Is this course the first part/course in Math applied to CP? Can we expect other topics in the next course(s)?

[@mahipalsingh-yo4jt]

great explanation!!!

[@hastar4329]

I have enrolled in the dsa course by gfg. I have done the first two sections and sir has only taught about the seive of eratosthenes. Is this topic explained in the course later?

[@subhashpatel5861]

can you please share the course with me :)

[@jdgoel4817]

Is that advanced programing I am just a begginer who started with ds algo

[@baldcoder_]

I don't see how this would solve the space complexity problem if the "low" is actually zero. We still need to initialize an array from zero to high (which is what we do in normal sieve).

[@chadmemes6905]

Not working for h>10^7.

[@chitranshjain9714]

for(long long j=i*i ; j

[@laraibanwar1618]

Really nice sir

[@nikhil6842]

Never saw such an easy explaination for such an advanced topic

[@GeeksforGeeksVideos]

We glad you liked it, Geek !

[@nikhil6842]

@@GeeksforGeeksVideos please extend my thanks to Sandeep sir, for revolutionizing education industry and providing a path for us hopeless College students

[@dakshkalucha5408]

How is space complexity theta(h)??

[@bhargavanand7325]

vector prime; void seive(int n) { vector isPrime(n+1,true); for(long long int i=2;i