Sieve of Eratosthenes | Journey into cryptography | Computer Science | Khan Academy
ฝัง
- เผยแพร่เมื่อ 28 เม.ย. 2014
- Sieve of Eratosthenes allows us to generate a list of primes.
Watch the next lesson: www.khanacademy.org/computing...
Missed the previous lesson? www.khanacademy.org/computing...
Computer Science on Khan Academy: Learn select topics from computer science - algorithms (how we solve common problems in computer science and measure the efficiency of our solutions), cryptography (how we protect secret information), and information theory (how we encode and compress information).
About Khan Academy: Khan Academy is a nonprofit with a mission to provide a free, world-class education for anyone, anywhere. We believe learners of all ages should have unlimited access to free educational content they can master at their own pace. We use intelligent software, deep data analytics and intuitive user interfaces to help students and teachers around the world. Our resources cover preschool through early college education, including math, biology, chemistry, physics, economics, finance, history, grammar and more. We offer free personalized SAT test prep in partnership with the test developer, the College Board. Khan Academy has been translated into dozens of languages, and 100 million people use our platform worldwide every year. For more information, visit www.khanacademy.org, join us on Facebook or follow us on Twitter at @khanacademy. And remember, you can learn anything.
For free. For everyone. Forever. #YouCanLearnAnything
Subscribe to Khan Academy’s Computer Science channel: / channel
Subscribe to Khan Academy: th-cam.com/users/subscription_...
I just did this up to 100k. I started at the start of quarantine.
Yeh
I was surprised that I could use javascript to compute up to 10m almost instantly.
@@christosbinos8467 Yeah I did up to a billion on python
@@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
Wonderful. Clear explanation, I liked the brief background for context, and the description was helpful and the perfect level of detail. Thank you.
What a beautiful thing!!! If this is not enlightenment I don't know what is.
This was a perfect explanation, thank you!!
WOW I UNDERSTAND EVERYTHING
Good Video. I forgot how it worked but you reminded me again. Thanks a lot!
Thanks!
great video..
Thank you.
super cool
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
Here is the Program code:
th-cam.com/video/sx3Cw14XZoc/w-d-xo.html
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?
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
0:10
can you explain its complexity
O(sqrt(n))
O(n log(log(n)))
Why start at n^2 ?
you won’t find any primes under n (the point of the sieve) by starting at n^2.
what is the range of long in java
From -2^63 to (2^63)-1
@@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
Holaaaaaa
Sorry if this is a noob question. Why it must use square root of n? Why square root?
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
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.
What does he mean by "unmarked"?
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.
hi from leetcode :D
based
Just see Dream yt
65 is composite
Thanks i needed to cheat on my homework cause its 10 pm RN so yea THANK YA
Why would you cheat
Lol
I made a python program with this and can you tell me if this is the same? (Ask me for the code)
65 is not prime
Why is it a bit confusing
oaaaaaaaaaaaaaa
Lol imagine top comment being with 5 likes
Com-Paw-sit. Not compuhzit. So cringey.