7 ms·
Where "fast" is defined as "involves disk reads" and "prime numbers" should have the qualifier "under 200." The algorithm is brute force testing of all values u
by dalke 16y ago
Where "fast" is defined as "involves disk reads" and "prime numbers" should have the qualifier "under 200." The algorithm is brute force testing of all values up to sqrt(n), which is worse than the one the ancient Greeks used.
- stcredzero 16y agoIf you want to deal with "real man's" prime numbers (those large enough to be used for secure cryptography) there are fast probabilistic tests which can quickly ensure confidence greater than the probability of your machine not getting blown up by lightning. http://en.wikipedia.org/wiki/Primality_test http://en.wikipedia.org/wiki/Primality_test
- joemanaco 16y agoyes, it's brute force, and the there are much faster algorithms. I just wanted to show, that it's possible to move expensive calculations to compile time with C++ Templates.
- dalke 16y agoThen the article is woefully mistitled. If I was doing this in C I would just write the code to generate a static table, so this isn't that useful of an good example except as very basic pedagogy. Also, you should show how the compiler time increases if you want it to compute, say, the 200th prime.
- joemanaco 16y agoHmmm, I'm thinking you're right. I've renamed it to "How to move prime calculation from execution to compile time". I hope this title fits better with the content.
- dalke 16y agoHey, this is HN. We're supposed to argue and talk past each other with no changes in what we've done or believe. ;) (And yes, it does fit better.) Cheers.