Sieve of eratosthenes

The sieve of eratosthenes is one of the most commonly asked mathematical programs for both coding round as well as interviews for placements and internships. While i explained this algorithm, i have showed 2 optimizations with reason and example, which will immensely improve the time complexity of sieve of eratosthenes to NloglogN.This method is used to find all the prime numbers till a given number N. The range to which this sieve algo can find all primes is limited by the memory allocated for the program to run. If you have large memory then you can create large sieve using array and run this algo to find all prime numbers till N. We can also serve range query for prime numbers and return primes in given range of X to Y. CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
TIME COMPLEXITY PROOF: www.geeksforgeeks.org/how-is-...

[@manasvinsharma1740]

This is the only channel that has explained the concept that why to start the inner loop from i^2 & why to stop the outer loop at sqrt(n). 🤩🤩

[@techdose4u]

🔥

[@anshumaan1024]

bhai mene gfg ki video dekhi..dimaag crash kr gya tha

[@md_nawshin_zaman]

The exact video I was looking for. Thanks for the great video.

[@ashutoshsinghpatel196]

Great respect for you & your explanation of algorithms.🙏

[@brycejohansen7114]

You could write "i * i

[@pragyan394]

The compiler would optimise that by itself

[@lavishyadav6756]

I must say, you can get solution from anywhere but the thinking to solve a new problem can be easily built by looking at your approaches towards problems. Well explained.

[@techdose4u]

Thanks

[@abdulhannan288]

This is a very underrated channel this is a very under rated channel

[@vishaldevasi3500]

One thing is clear that u are a Genius...🔥👍🏽

[@upsolver2342]

Buddy u r awesome, u build very deep understanding and intuition of logic. Thanks for such explanations.

[@techdose4u]

Welcome 😀

[@user-lh7rv1ts3u]

Thank you so much, it helped on my C++ course

[@mdzaid3792]

The explanation is literally Supercalifragilisticexpialidocious 🔥🔥🔥

[@techdose4u]

What's this word bro 😅

[@surajbaranwal56.]

great job sir, well explained, easy, understandable.

[@anuragsoni2256]

Very nice problem. Thanks!

[@gabrieldjebbar7098]

Awesome explanation for the optimization ;)

[@techdose4u]

Thanks

[@Justdoing185]

Excellent explanation sir

[@mounikanandimalla9321]

That was a super explanation:)

[@techdose4u]

Thanks :)

[@akansha1127]

Tysm Sir the best explanation I ever had till now I immediately subscribed to your channel because I know this will be very very useful for me .. Once again thank you Sir.

[@techdose4u]

Welcome :)

[@DEEPAKSAHU-ou4jy]

ek no guruji

[@sourav9135]

Thanks for this video but can you tell how to do this in O(n) Time complexity

[@MrMonishSoni]

This is Exactly what a Good Video would look like, no extra animated stuffs only to the point. Because once the concept is clear code part is easy. Btw i would like to add here that i think sieve should me modified for odd numbers only because all the multiples of 2 i.e. 2n are anyways not prime. So Optimized Sieve = Classic Sieve + Till Root n + Odd Numbers Only.

[@techdose4u]

Right. The numbers are already marked and so will not be processed again. I think you are suggesting to jump in values of 2 rather than 1 right ? It's a good idea to not even have to check it :)

[@MrMonishSoni]

@@techdose4u Ya I mean i have read it somewhere on wiki page i think because it effects on the time/space complexity. Although there are much complex sieves which are still more optmized, and i didnt get that, but as far as this video goes. this is perfect. Thanks.

[@MrMonishSoni]

@@techdose4u Also Prime Numbers are utterly the most important concept like i have came after going through some project Eulers problem and what i had observed is that it take huge understanding of just basic maths like prime numbers to just implement an efficient algorithm. Because the Numbers on project Eulers goes upto millions for primes just to make sure you dont write an inefficient code. ;) :)

[@techdose4u]

I will cover that when I start Number theory playlist :) Concepts of primes and complex sieves.

[@shivrajahirwar4334]

very nice explanation:)

[@mohitkhandelwal5050]

what will be the time complexity of FIRST METHOD of sieve of eratosthenes ??????

[@techamet428]

beautifully explained

[@techdose4u]

Thanks

[@tanmaytyagi7031]

Very nicely explained ❤️

[@techdose4u]

Thanks 😊

[@karankanojiya7672]

TYSM SIR! Respect ++ !

[@madhupadayeswanth1865]

sir i could not understand why we need to take upto sqrt(N) in first loop

[@Amaim123]

Well explained

[@melvinkimathi8924]

hey Techdose, what's the name of the software that you are using to explain your code?

[@jigyasakodnani3872]

Thanks for this video, you're explanation is amazing 😃

[@techdose4u]

Welcome :)

[@AinasDiaries]

At 3:52 why take j

[@ruthvikmankari1340]

Thank You

[@techdose4u]

Welcome :)

[@vijaykumarlokhande1607]

where is segmented sieve with O(n) complexity?

[@herculean6748]

Thanks

[@techdose4u]

Welcome :)

[@sahilgore7645]

how to prove that the factor

[@swastikpadasalkar5765]

Happy to see tricolors in the beginning .💜

[@techdose4u]

😅

[@sivaganesh4489]

Awesome please do more videos on these type of questions

[@techdose4u]

Thanks :)

[@ujjwalprazapati8480]

The outer for loop is making sqrt(n) iterations. So, why the complexity isn't sqrt(n)LogLogn instead? Correct me if I am wrong. And Thanks for such a good explanation :)

[@ganeshkamath89]

I think that is because each identified number goes and marks all other multiples, thus iterating till end.

[@mandeep2192]

explained beautifully...

[@techdose4u]

Thanks :)

[@harsimrankaur653]

Great explanation!

[@neghatnazir1668]

thanks for this video its helpful

[@techdose4u]

Welcome :)

[@aryaman_godara]

your color scheme was already aligned for "Independence day : azadi ka amrit mahotsav" 😂😂 kool video though

[@chiranjeevichiru8327]

J=j+i; how it increment

[@harshpatel1385]

god bless you

[@techdose4u]

:)

[@ALEEMKHAWAR1]

here I know only why to start inner loop from i^2 & outer loop upto SQRT N

[@divyanshusalve8173]

Nice video, although I came to see geeksforgeeks version of optimized version sieve of eratosthenes, I got a hint from this video about gfg's solution. A like for that also..

[@techdose4u]

Nice

[@harshpatel1385]

plz make playlist on dynamic,tree,graph

[@techdose4u]

Doing so

[@Cybernetic1]

You are the best 💝💌

[@techdose4u]

Thanks :)

[@vickycsk1998]

it is not applicable for 10^12

[@MohamedMahmoud-dn5pm]

good way.....thanks

[@techdose4u]

Welcome :)

[@sarthakgupta1263]

amazing exlpanations

[@techdose4u]

Thanks :)

[@sambhumahato8320]

Awesome❤️

[@techdose4u]

:)

[@khageswarmalakar2011]

Thank you

[@techdose4u]

Welcome

[@utubecom9185]

Sir, i have a doubt and i have put that doubt on candy distribution problem video . Sir i am waiting for the reply .......

[@techdose4u]

Okay let me check.

[@shashib16]

what if, N=40 and 35 is not divisible by 2 & 3.

[@techdose4u]

Then you will mark mutiples of next prime number which is 5.

[@happypuppy3281]

Please Make a video on sieve of atkins.

[@techdose4u]

Yea sure

[@supernova7870]

First viewer

[@techdose4u]

:)

[@harshpatel1385]

can you make video of solution of leetcode

[@techdose4u]

I will do it whenever I get time.

[@shaswatdas6553]

Python code incoming.. from math import sqrt def sieve(n): if n < 2: return [] ar = [True for i in range(n+1)] p = [] for i in range(2, int(sqrt(n))+1): if ar[i] is False: continue for j in range(i**2, n+1, i): ar[j] = False p=[i for i in range(n) if i>=2 and ar[i]] return p n = 19 print(sieve(n))

[@techdose4u]

👍

[@mdfahadkhan518]

No ,, your logic is wrong. We can continue the loop till Square Root of number