4 ms·
It doesn't matter much for his test, because the compiler won't optimize it, but one can simplify the loop to only go from 2...n/2+1 e.g. change the line to: f
by briHass 11y ago
It doesn't matter much for his test, because the compiler won't optimize it, but one can simplify the loop to only go from 2...n/2+1 e.g. change the line to:
for(int a=2; a<n/2+1; a++)
That would be the obvious optimization, since 2 is your smallest factor, a factor can't be larger than half your number. In actuallity, knowing a little math gives you that if a factor is > the square root of n, there's a factor smaller than that. So:
for(int a=2; a<sqrt(n)+1; a++)
- occamrazor 11y agoAnd it would be better to move the sqrt(n) calculation outside of the loop (I guess that any decent compiler would make this simple optimisation anyway)
- briHass 11y agoYeah, that would only be evaluated once, since the value of n doesn't change inside the loop.
- nivertech 11y agoI think it should be something like: test for all even numbers only once + uint last = ceil(sqrt(n)); for(uint a=3; a<=last; ++a,++a)