I know you mentioned it in the video, but using a the Sieve of Eratosthenes for larger values of n ( Say, over 10 million), would be a lot faster. You either use it to generate a very large list of primes up to n and check if n is present, or you could have it generate a very large amount of primes to use as prime factors to check the divisibility of other numbers. Just make sure to manipulate the list of primes to be less than N before using it as an array in the for loop.
@@LateCodeParty Memoization is something else entirely. Sqrt is a single instruction in x86 machines, just as fast as a float multiplication. I'll tell you more: probably computing the sqrt is better than doing the i*i < n check you suggest, because doing the latter you perform a multiplication at each iteration, while the sqrt you calculate it once at the beginning and are done with it. In more practical terms, the difference between these two options is most likely insignificant. Worrying about these microopotimizations is pointless most of the time.
@LateCodeParty here is the benchmark that proves d*d leads to the exact same performance as sqrt: gist.github.com/cacharle/db4faaad837d9ee0d0ca2b7d7aaa95d8
The main reason why 1 is not considered a prime number is the fundamental theorem of arithmetics: every integer has a unique factor decomposition into prime numbers. If 1 were a prime number, the theorem could not be stated in so simple terms, because you could add to the prime decomposition of n 1 raised to any arbitrary power and it would be still a valid decomposition for n. For many theorems you would need to make an exception for 1: "for any prime number p except 1...". Very messy. Yet another argument is that prime numbers can be divided by exactly 2 naturals: 1 and themselves. 1 on the other hand can only be divided by 1 number, which is 1.
Kekw, that video was recommended to me cuz I love m*th (a ? e) and programming. I'm tired of these guys-like YT programmers who don't give a fuck about what they say. Fortunately but I didn't learn anything new. However, I can say that this person is definitely a programmer (at least the link to the gh **screams** about it) and does videos for PROGRAMMERS, not for ordinary "programmers" (I mean the way of explanation). It's a true content, please keep making videos. It would be nice to see more complex topics
@@InconspicuousChap godbolt.org/z/ronredas8 It seems like the sqrt is computed before the main loop (.L7) But the assembly differs if I declare the sqrt above the loop or if I make n const so I'll benchmark later to make sure
@@InconspicuousChap even if the sqrt were calculated at each iteration (which shouldn't be the case for a good optimizing compiler), yes, indeed, it'd be faster. Sqrt is a single instruction in x86 assembly, and you would be needing far less iterations. Imagine you were checking if 1000001 is prime. It's better to perform 500 sqrts than 500000 integer divisions. It's often easier to get lost in the small costs of insignificant things rather than seeing the bigger picture, in this case, asymptotic costs. So yes, it's a fast approach by all accounts and measures. Not the fastest tho. It's still prohibitively slow for big numbers (e.g. 2000 bit numbers). For those you would need better algorithms like probabilistic primality testers.
Best coding channel on YT rn
"Best" is a bit much but thank you very much anyway 😄
I know you mentioned it in the video, but using a the Sieve of Eratosthenes for larger values of n ( Say, over 10 million), would be a lot faster. You either use it to generate a very large list of primes up to n and check if n is present, or you could have it generate a very large amount of primes to use as prime factors to check the divisibility of other numbers.
Just make sure to manipulate the list of primes to be less than N before using it as an array in the for loop.
That French access is something truly marvelous, chef's kiss
instead of using " d
He's not recursively or repeatedly calling the function, it won't benefit from memoization
@@LateCodeParty Memoization is something else entirely. Sqrt is a single instruction in x86 machines, just as fast as a float multiplication. I'll tell you more: probably computing the sqrt is better than doing the i*i < n check you suggest, because doing the latter you perform a multiplication at each iteration, while the sqrt you calculate it once at the beginning and are done with it. In more practical terms, the difference between these two options is most likely insignificant. Worrying about these microopotimizations is pointless most of the time.
@hemartej thanks for the thorough reply, I approve
@LateCodeParty here is the benchmark that proves d*d leads to the exact same performance as sqrt: gist.github.com/cacharle/db4faaad837d9ee0d0ca2b7d7aaa95d8
Your videos are very insightful man, thanks!
I'm glad you learned something 🙂
That’s awesome great ideas
The main reason why 1 is not considered a prime number is the fundamental theorem of arithmetics: every integer has a unique factor decomposition into prime numbers. If 1 were a prime number, the theorem could not be stated in so simple terms, because you could add to the prime decomposition of n 1 raised to any arbitrary power and it would be still a valid decomposition for n. For many theorems you would need to make an exception for 1: "for any prime number p except 1...". Very messy.
Yet another argument is that prime numbers can be divided by exactly 2 naturals: 1 and themselves. 1 on the other hand can only be divided by 1 number, which is 1.
Ah yes, I remember learning that at some point, makes sense, thanks for the refresher 🙂
Kekw, that video was recommended to me cuz I love m*th (a ? e) and programming. I'm tired of these guys-like YT programmers who don't give a fuck about what they say. Fortunately but I didn't learn anything new. However, I can say that this person is definitely a programmer (at least the link to the gh **screams** about it) and does videos for PROGRAMMERS, not for ordinary "programmers" (I mean the way of explanation). It's a true content, please keep making videos. It would be nice to see more complex topics
I am indeed a PROGRAMMER, thx and more complex topic are planned (mostly programming complex, less math complex)
@@cacharle happy to hear that. Math is good also, sometimes it's important to do some math tasks just to be sure that you didn't forget how to do it
mate this neovim themeee, whats the name??
The theme is gruvbox
Calculating d
Bruh, that's obviously taken care of by the compiler..
@@cacharle do you have an assembly listing proving that?
@@InconspicuousChap godbolt.org/z/ronredas8
It seems like the sqrt is computed before the main loop (.L7)
But the assembly differs if I declare the sqrt above the loop or if I make n const so I'll benchmark later to make sure
@@InconspicuousChap even if the sqrt were calculated at each iteration (which shouldn't be the case for a good optimizing compiler), yes, indeed, it'd be faster. Sqrt is a single instruction in x86 assembly, and you would be needing far less iterations. Imagine you were checking if 1000001 is prime. It's better to perform 500 sqrts than 500000 integer divisions. It's often easier to get lost in the small costs of insignificant things rather than seeing the bigger picture, in this case, asymptotic costs.
So yes, it's a fast approach by all accounts and measures.
Not the fastest tho. It's still prohibitively slow for big numbers (e.g. 2000 bit numbers). For those you would need better algorithms like probabilistic primality testers.
@@hemartej Thanks for the answer, I am looking into probabilistic methods at the moment and I'll do a video about them in the future 😃