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

GeeksforGeeks presents you the Sample Video II for Essential Mathematics for CP.
Link for the course mentioned above - practice.geeksforgeeks.org/co...
Our courses : practice.geeksforgeeks.org/co...
Please Like, Comment and Share the Video among your friends.
Install our Android App:
play.google.com/store/apps/de...
If you wish, translate into the local language and help us reach millions of other geeks:
kzbin.info_cs_p...
Follow us on Facebook:
/ gfgvideos
And Twitter:
/ gfgvideos
Also, Subscribe if you haven't already! :)

[@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 🙂.

[@leepakshiyadav1643]

Amazing explaination 👏👏

[@anuraggulati2167]

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

[@mahipalsingh-yo4jt]

great explanation!!!

[@chinmaydeshpande8969]

Best explanation Sir thank you!

[@codingmaster008]

thanks sandeep sir for the awesome explaination👍

[@shivamkumarsingh667]

Best Explanation 🙌

[@HappyHappy-ih5zp]

Ek baar mein samjh aa gya Thanks Sir.

[@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.

[@laraibanwar1618]

Really nice 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

[@jdgoel4817]

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

[@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.

[@MrMadcatsam]

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

[@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).

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

[@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

[@chitranshjain9714]

for(long long j=i*i ; j

[@user-wg6fs5vg3c]

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

[@chadmemes6905]

Not working for h>10^7.

[@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 :)

[@dakshkalucha5408]

How is space complexity theta(h)??

[@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

[@bhargavanand7325]

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