Sieve of Eratosthenes | Journey into cryptography | Computer Science | Khan Academy

[@Dimension5Productions]

I just did this up to 100k. I started at the start of quarantine.

[@learningandgamingwithsaach8413]

Yeh

[@christosbinos8467]

I was surprised that I could use javascript to compute up to 10m almost instantly.

[@Dimension5Productions]

@@christosbinos8467 Yeah I did up to a billion on python

[@hil449]

@@christosbinos8467 ofc, the standard sieve runs in O(n * log(log(n))), thats extremely fast, in c++ you'de be able to calculate up to 10^9 in one second

[@ryanventurino3578]

Wonderful. Clear explanation, I liked the brief background for context, and the description was helpful and the perfect level of detail. Thank you.

[@aadil4236]

What a beautiful thing!!! If this is not enlightenment I don't know what is.

[@DavidaThatch]

This was a perfect explanation, thank you!!

[@Silberdragon1]

Good Video. I forgot how it worked but you reminded me again. Thanks a lot!

[@Ali_Emran]

WOW I UNDERSTAND EVERYTHING

[@IshraqTanvir]

Love y'all ! just wow ...

[@attilatoth1396]

Thanks!

[@satishkumarsingh7354]

Number in this sives use to repeat. Is it possible to avoid repeat?

[@lycan2494]

great video..

[@ulti72]

can you explain its complexity

[@FilipeSilva1]

O(sqrt(n))

[@fovibhaassrivastava4951]

O(n log(log(n)))

[@Wahee1]

0:10

[@avoriginal9342]

The pseudocode I’m failing to understand, so from 2 till sqrt of n if a is unmarked then a is prime, 2 will be unmarked, which makes it price, now for all multiples of 2, 4-6-8 etc are marked as composite, then 3 and starting from 9 to n, so at what point do we check for example 79 if we are only checking from 2 until sqrt(n), if we picked n=100 then we’d only check until 10, so what about all the number after 10 that are not marked as composite, and nowhere does it say we are checking them

[@hansangjung6063]

Thank you.

[@maxfromukraine1630]

What does he mean by "unmarked"?

[@fovibhaassrivastava4951]

In code, it would mean an array of booleans where all values are set to true. Each time we find a composite, we mark it by changing its value to false.

[@aelng1681]

super cool

[@AbhishekVerma-zt7nu]

Why start at n^2 ?

[@aydc6740]

you won’t find any primes under n (the point of the sieve) by starting at n^2.

[@moonman239]

I wonder about something. Would it be faster to check if n is prime if, instead of listing all the primes, we calculated the row and column on which the number would lie and then used that information to check if the number is prime? For example, 27 is on row 3 column 7 (or, row 2 column 6 if you're doing zero-based indexing) What if we tried using that information to decide if 27 is prime?

[@yajaman]

If the information about whether a prime is encoded in its row and column value, you would be able to solve the twin prime conjecture

[@thelast2233]

what is the range of long in java

[@peiceofcheese87]

From -2^63 to (2^63)-1

[@thelast2233]

@@peiceofcheese87 one more question that i really stuck right now also when I see problem there is constrian like 10 ^5 and I count with t if required I know big o and I know how o(n^2) work like two loops n times goes and more on it 1 st problem is 10 ^5 means this range 100000 but we have interger range 2^63 second is when I saw constarin I got idea that I need long for 10^16 but how can I know this time bruteforce works as begginer my code will very length and many time miss edge case and so on so what should i do? Do I need to see any video or how do I practice also is akrbra bazzi formula helps

[@yafethtb]

Sorry if this is a noob question. Why it must use square root of n? Why square root?

[@file4318]

Because factors come in pairs. Take for example 16. One pair would be 1, 16... another 2, 8... 4, 4... notice they intesect on the square root (4*4=16). This means a factor cannot be above the square without having a factor pair below it. And therefore if there is no factors below the square root there can be none above either

[@the_m_original]

suppose n is the maximum number you use to get primes. (primes up to n, suppose its 100) and p is the unmarked number you are using to mark out multiples at p = 2, you use the square of that number (2^2 = 4) to get the starting point for multiples of p. then you repeat, as explained here, to look for unmarked numbers (p = 3, p^2 = 9, so start the multiples counter at number 9.) then, as ALSO explained here, once p reaches 11 and n is 100, the square of p will be larger than n, which we dont want, so we stop, right where p is nearby the square root of n or 100, which is 10.

[@bharathiDevi001]

Here is the Program code: kzbin.info/www/bejne/qamWdKpnab2NpcU

[@michaelfortanely5715]

based

[@Progamer-wt9ir]

Just see Dream yt

[@waffles_1823]

65 is composite

[@pablocarames3261]

Holaaaaaa

[@sarlarnsulonundedesi5913]

hi from leetcode :D

[@cait1yn_]

Thanks i needed to cheat on my homework cause its 10 pm RN so yea THANK YA

[@HiteshLadla]

Why would you cheat

[@Progamer-wt9ir]

Lol

[@0_-]

I made a python program with this and can you tell me if this is the same? (Ask me for the code)

[@raresaturn]

65 is not prime

[@marieconpacuribot2718]

Why is it a bit confusing

[@Mylok_]

oaaaaaaaaaaaaaa

[@Progamer-wt9ir]

Lol imagine top comment being with 5 likes

[@darquenite]

Com-Paw-sit. Not compuhzit. So cringey.