3 ms·
FWIW, (i < n) can be replaced by (i <= floor(sqrt(n))) to avoid unnecessary iterations.
by gerty 10y ago
FWIW, (i < n) can be replaced by (i <= floor(sqrt(n))) to avoid unnecessary iterations.
- OskarS 10y agoYeah, obviously, there are lots of ways to improve that code. First off all, much more efficient to to do (i * i <= n) instead of (i <= sqrt(n)), or at the very least you can cache sqrt(n) so you don't recalculate it every step. You can also do a separate test for 2, then start at 3 and use i+=2 instead of i++, that cuts the test time in half. Once you've done that, you can observe that all primes are 6k +/- 1 except 2 and 3, which makes your code 3 times faster than the naive version. At this point, you've basically got a simple wheel primality testing algorithm going, so why not go all the way? I don't think the parent poster was making the point that his was the most efficient algorithm for testing primes. I think his point was that regular numbers are O(log n) in CS terms, not O(1), which is not obvious at first.