Hello, mathematician here. Your method is awesome, but you only need to check for divisors up to the floor of sqrt(p), what i mean is, if you wanna check if one thousand is prime, you only need to check if 1000 is divisible by the numbers 2 to 31 (square root of 1000). Hope this helps, this makes it a lot faster.
Thank you for the video! I love quick little algorithm comparison showcases. A quick note: on my machine, my own version of the trial division algorithm (up to 1 million) took 12 seconds to run while printing the numbers and just over one second without printing the numbers. This is because system calls (which are required to print to the terminal) are around a thousand times (or more!) slower to run than typical math operations, depending on the language and environment. This also explains why the sieve and trial division algorithms took about the same time for the first million primes, they both spent most of the time printing instead of actually doing math. It's worth keeping this in mind for future comparisons. Again, thank you for the video; I would love to see more naive vs. advanced algorithm implementation comparisons!
Hi! Really glad to hear that you enjoyed the video😊 I’ve also tried the algorithm without printing and realised they were quicker, however I felt like it would be a little more visually interesting if the prime numbers were printed out in the video 😅
The algorithm explanation is genuinely super easy. Great job as always :D Also a quick question; if we use a faster compiling language than python will the time change be noticeable or same?
Thanks!🙏🏻 Yes the time difference if we use a faster language (e.g C/C++) should be noticeable! I just used python because it’s the language I am most familiar with 😁
I think, the main problem with faster algorithms here is results output. Most of the time this code would spend printing the results. If it is true, the way of working with i/o is more important (in terms of performance) than programming language choice
Yes, I actually did this a while back with 3 languages and this sieve. Nodejs, C++, and Python Also, a quick note, these tests were automated back to back, mixing the order. along with that I did not have each number printed into the console because printing, especially on Windows, is slow. On going to 1m, and averaged over 5 times, the times were: Python: 1797.4 ms Node: 149.8 ms (12x faster) C++: 46.7 ms (38.4x faster) then for 10m, again averaged over 5 times: Python: 23752.1 ms Node: 1214.1 ms (19.6x faster) C++: 699.8 ms (33.9x faster) Also, here are the peak ram usages going from the 1m run, then 10m run, were Python: 86.7 mb, 772.9 mb Node: 36.6 mb, 119.7 mb C++: 4.9 mb, 15.6 mb C++ is so much better here btw because I used bit arrays (std::vector), basically each number bool takes up a single bit in the array. (this is how the sieve works btw)
There is a way to make the Sieve of Eratosthenes faster (many ways, but I'll focus on one): Consider the product of the first six primes (the sixth primorial, or 2*3*5*7*11*13). We can calculate the gcds of all numbers less than it. If the gcd is not one, it must share a factor, and thus be composite. Since these gcds repeat mod this product (call it p), we need only consider numbers of the form a + k*p, where a is a number where gcd(a,p) is 1, and k is an integer. You can then implement the sieve of eratosthenes to work from there, without needing all those other redundant checks.
String conversion is pretty slow and Python isn't very fast either, but printing the primes after performing the sieve would reveal it's much faster than that. I've done this in another programming language and it can perform the sieve method on all numbers up to 100 million in about 800ms, and up to 1 billion in about 10 seconds. It achieves this by simply ignoring all even numbers, multiples of 5, and when doing the marking step, where you start with a p prime and mark all of its multiples, just increment by p * 2 to only mark the odd ones since we already know the even numbers (besides 2) are composites (= not prime). I've done this in Visual Basic and added a visualization too, but doing this in C would make calculating billions of primes in a matter of a few seconds possible.
Good catch, this was actually an oversight when I made the video. The trial division algorithm actually had the square root as the limit, I just forgot to explain it during the video. Hope that answers your question!
Question: Does the respective script exclude numbers ending in 0, 2, 4, 5, 6, 8? Because these are certainly not prime numbers. Where can I get the scripts?
horrible timing, the main slowdown for the last 2 algorithms was just printing out all those numbers. did the same thing without printing and just counting and got the 10 million prime numbers in 25 milliseconds 🙂
Hello, mathematician here. Your method is awesome, but you only need to check for divisors up to the floor of sqrt(p), what i mean is, if you wanna check if one thousand is prime, you only need to check if 1000 is divisible by the numbers 2 to 31 (square root of 1000). Hope this helps, this makes it a lot faster.
If you check the code, this was already implemented, just not mentioned verbally
Thanks for the feedback! But yes I did implement this, just not for the first algorithm 😁
We be obtaining security keys used by big internet security firms with this one 🗣️🗣️🗣️🔥🔥🔥🔥💯💯💯
ok..
primes are in P
Thank you for the video! I love quick little algorithm comparison showcases. A quick note: on my machine, my own version of the trial division algorithm (up to 1 million) took 12 seconds to run while printing the numbers and just over one second without printing the numbers. This is because system calls (which are required to print to the terminal) are around a thousand times (or more!) slower to run than typical math operations, depending on the language and environment. This also explains why the sieve and trial division algorithms took about the same time for the first million primes, they both spent most of the time printing instead of actually doing math. It's worth keeping this in mind for future comparisons. Again, thank you for the video; I would love to see more naive vs. advanced algorithm implementation comparisons!
Hi! Really glad to hear that you enjoyed the video😊 I’ve also tried the algorithm without printing and realised they were quicker, however I felt like it would be a little more visually interesting if the prime numbers were printed out in the video 😅
underrated channed. this video is so good. Would you like to do more number algorithms showcase like this. I'd love to watch!
Thank you! ☺️
The algorithm explanation is genuinely super easy. Great job as always :D
Also a quick question; if we use a faster compiling language than python will the time change be noticeable or same?
Thanks!🙏🏻 Yes the time difference if we use a faster language (e.g C/C++) should be noticeable! I just used python because it’s the language I am most familiar with 😁
@@MarshySyntax ah I see. Thanks for answering. Cause I am studying programming so these kinda videos and questions help :D
I think, the main problem with faster algorithms here is results output. Most of the time this code would spend printing the results. If it is true, the way of working with i/o is more important (in terms of performance) than programming language choice
It's probably around 10x the speed
Yes, I actually did this a while back with 3 languages and this sieve.
Nodejs, C++, and Python
Also, a quick note, these tests were automated back to back, mixing the order.
along with that I did not have each number printed into the console because printing, especially on Windows, is slow.
On going to 1m, and averaged over 5 times, the times were:
Python: 1797.4 ms
Node: 149.8 ms (12x faster)
C++: 46.7 ms (38.4x faster)
then for 10m, again averaged over 5 times:
Python: 23752.1 ms
Node: 1214.1 ms (19.6x faster)
C++: 699.8 ms (33.9x faster)
Also, here are the peak ram usages going from the 1m run, then 10m run, were
Python: 86.7 mb, 772.9 mb
Node: 36.6 mb, 119.7 mb
C++: 4.9 mb, 15.6 mb
C++ is so much better here btw because I used bit arrays (std::vector), basically each number bool takes up a single bit in the array. (this is how the sieve works btw)
Great video as always, i really enjoy watching your videos. Keep the great work up!
Thank you for your support!
I mean I really would like to see more of the code, but other than that, it's very easy to understand
Thank you! I’ll keep that in mind 🙏🏻
There is a way to make the Sieve of Eratosthenes faster (many ways, but I'll focus on one):
Consider the product of the first six primes (the sixth primorial, or 2*3*5*7*11*13). We can calculate the gcds of all numbers less than it. If the gcd is not one, it must share a factor, and thus be composite. Since these gcds repeat mod this product (call it p), we need only consider numbers of the form a + k*p, where a is a number where gcd(a,p) is 1, and k is an integer. You can then implement the sieve of eratosthenes to work from there, without needing all those other redundant checks.
Wow I never thought of this, interesting!
Nice video! I like your explanations because they are really simple and easy to understand!
Thank you!
String conversion is pretty slow and Python isn't very fast either, but printing the primes after performing the sieve would reveal it's much faster than that.
I've done this in another programming language and it can perform the sieve method on all numbers up to 100 million in about 800ms, and up to 1 billion in about 10 seconds.
It achieves this by simply ignoring all even numbers, multiples of 5, and when doing the marking step, where you start with a p prime and mark all of its multiples, just increment by p * 2 to only mark the odd ones since we already know the even numbers (besides 2) are composites (= not prime).
I've done this in Visual Basic and added a visualization too, but doing this in C would make calculating billions of primes in a matter of a few seconds possible.
Super easy to understand, would love to see more complex subjects
Thanks! I’ll try to keep them coming!
I did this as my first ever project!!!!! I did the "trial" thing i think i got like 2 million numbers parsed in a second
That’s awesome! 😁😁
I thought this is a channel with a million subscribers, really high quality video ,l like it
Thank you! I try my best to make as good videos I can 😊
Really good video, however the voice goes straight through me.
Thanks for the feedback! Very much appreciated 🙏🏻
I was late but great video again
😆 Thank you as always!
Hi, just a quick question for trial division algorithm why you had calculated square root as limit
Good catch, this was actually an oversight when I made the video. The trial division algorithm actually had the square root as the limit, I just forgot to explain it during the video. Hope that answers your question!
@@MarshySyntax Thanks for the solution!! Btw, very good video!!
Thank you!
Question: Does the respective script exclude numbers ending in 0, 2, 4, 5, 6, 8? Because these are certainly not prime numbers. Where can I get the scripts?
Nope! It does not explicitly exclude those numbers. But when the script is run it’ll naturally figure out that these aren’t primes
@@MarshySyntax The script can be faster. It don't need time for checking 0, 2, 4, 5, 6, 8 if the number has millions of digits.
The voice is paintful to listen to, but good video
Thank you for that feedback! 😊
@@MarshySyntax no problem
Great content just change the voice
Thanks for the feedback!
wtf is this voice
horrible timing, the main slowdown for the last 2 algorithms was just printing out all those numbers. did the same thing without printing and just counting and got the 10 million prime numbers in 25 milliseconds 🙂
also uh i was using rust cuz idk python so idk maybe bad comparision
yeap, noob :D