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?
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.
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.
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.
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.
@@GeeksforGeeksVideos please extend my thanks to Sandeep sir, for revolutionizing education industry and providing a path for us hopeless College students
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?
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).
One of the best explanation on Segmented sieve .
Thank you Shashank !
@@GeeksforGeeksVideos best explanation
With that level of explanation I solved it myself within 10 minutes. Seems like it was too easy. Awesome Sir❤
This is literally the best explanation video of gfg till now.
Simple and perfect video. Thank u, sir. GFG has made my life easy.
It's the best explanation I can get for segmented sieve. Thank you so much sir for this video
The Best explanation about segmented sieve. Thank you so much sir 🙂.
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?
Thanks, point 2 really helped a lot
Best explanation Sir thank you!
this video clears all the doubts..thankyou sir🙂🙂😇🥰
Ek baar mein samjh aa gya Thanks Sir.
Amazing explaination 👏👏
In void sieve function it should be
long long j=2*i ; j
I was also wondering the same thing.
Both are correct
j=i*i better optimisation ;
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.
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
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.
@@vaibhavjaiswal7811 Thanks I got stuck here.
@@vaibhavjaiswal7811 thanks bro !! case of 1 has to handled too!!
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.
thanks sandeep sir for the awesome explaination👍
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.
Best Explanation 🙌
Never saw such an easy explaination for such an advanced topic
We glad you liked it, Geek !
@@GeeksforGeeksVideos please extend my thanks to Sandeep sir, for revolutionizing education industry and providing a path for us hopeless College students
Is this course the first part/course in Math applied to CP? Can we expect other topics in the next course(s)?
great explanation!!!
Really nice sir
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?
can you please share the course with me :)
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).
sir in void sieve
in the for loop j++ should be replaced by j += i;
please correct me @GeeksforGeeksVideos
for(long long j=i*i ; j
Is that advanced programing
I am just a begginer who started with ds algo
vector prime;
void seive(int n)
{
vector isPrime(n+1,true);
for(long long int i=2;i
Not working for h>10^7.
How is space complexity theta(h)??