Prime Number Sieves

We discuss various prime number sieves such as the Sieve of Eranthoses, to find all primes from 1 to N.
We then talk about a segmented sieve approach, and discuss the time complexity for finding primes in a given range.

Code:

References:

[codex]

I am a visual learner and there are very few visual resources for competitive programming. Thank you for taking up the initiative! I find I learn much more by watching your videos than getting lost in walls of text explanations.

[rachit]

Hi, I am unable to get your point @5:00 where you say that " i > √n ". And then " i * √n <= n " can you please elaborate on it!! Where does this √n comes from and why we are checking values greater than √n. Thanks in advance.

[arjungurjar]

Nicely explained Gaurav Sen, I really appreciate your effort to make these videos to helping the ones who needed. If possible, could you please make a video on How to start a competitive programming for complete beginners. What are the basic to advanced things we need to learn to get proficient in programming.

[kevinbow]

Thanks for the great video. Did you check the sieve of Marouane? It avoids calculating the redundancy of odd composites

[heyitsprabal]

Hey Gaurav can you tell me why you have used j=j+(i*2) as the incrementation part instead of j=j+i like for 3 code takes leaps of 6, and for 5 it takes leaps of 10, for 7 it takes leaps of 14

[hennabuzzz]

I am bliss to watch this content!Thank you so much 😍

[ANUJSHARMA-nnpf]

Hi, Please anybody let me know. Where can we run the code of cp problems. Where we can see the space time complexity with custom inputs? Is there any online platform or can setup in vs code.

[Abdullahansari-vbnh]

bro you are doing great and i request you please explain the terms clearly like why you use root N and how its been used and etc. thank-you bro

[prakashmodak]

Hi
Prakash Modak from Pune.
How to find out Prime Numbers in given range of numbers?
Do you have any excel sheet where i can find out Prime Numbers in give range i.e. Prime numbers between 1000 to 3000.

[shyamdewkumar]

If you don't mind can you provide the question link 🔗.

[NohandleReqd]

Gaurav bhaiya.. from where and HOW do i understand bitwise sieve ? It is really getting over my head.

[Premsept]

For value like 62 the prime factors of 62 are 31, 2 but give only 2.
I think outer loop run up to N not only root N.

[shubhamverma]

Gentle reminder: at time 16:24, it is 39 not 37, so 3 will also come in the list and hence its frequencies...

[rajatagarwal]

I m a beginner! Do we check that 54 is divisible by 3 or 27 is divisible by 3?

[shivangipandey]

Hi Gaurav,

The video is pretty good and you made it really easy to understand. But I could not understand the time complexity?

[manan]

Please can you share some optimised code of basic algo. For cc.

[allenjamesvinoy]

Can you explain how you deduced the time complexity?

[coolDG]

19:41 Testing your mathematical skills ^^ 78/2 = 39 not 37 :D great video tho! thanks alot

[nimitjain]

Can anyone help me understand its time complexity of n(logn)(loglogn) ?

[jaypatel-mejo]

Every prime number can be written in form of 6k +- 1 except 2 and 3 but not all 6k +- 1 is prime number k