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

@learningandgamingwithsaach8413

3 жыл бұрын

Yeh

@christosbinos8467

2 жыл бұрын

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

@Dimension5Productions

2 жыл бұрын

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

@hil449

2 жыл бұрын

@@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.

This was a perfect explanation, thank you!!

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

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

WOW I UNDERSTAND EVERYTHING

Thanks!

great video..

Thank you.

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

super cool

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

Why start at n^2 ?

@aydc6740

Жыл бұрын

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

@peiceofcheese87

2 жыл бұрын

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

@thelast2233

2 жыл бұрын

@@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

What does he mean by "unmarked"?

@fovibhaassrivastava4951

7 ай бұрын

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.

can you explain its complexity

@FilipeSilva1

2 жыл бұрын

O(sqrt(n))

@fovibhaassrivastava4951

7 ай бұрын

O(n log(log(n)))

0:10

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

@file4318

2 жыл бұрын

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.

Here is the Program code: kzread.info/dash/bejne/paxnpdlqZLvAn8Y.html

hi from leetcode :D

Holaaaaaa

based

@Progamer-wt9ir

4 жыл бұрын

Just see Dream yt

65 is composite

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

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

@HiteshLadla

4 жыл бұрын

Why would you cheat

@Progamer-wt9ir

4 жыл бұрын

Lol

Why is it a bit confusing

65 is not prime

oaaaaaaaaaaaaaa

Lol imagine top comment being with 5 likes

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