3 ms·
A better implementation will only check to sqrt(n), as there can be no prime factor greater than that.
by jdmichal 12y ago
A better implementation will only check to sqrt(n), as there can be no prime factor greater than that.
- punee 12y agoYes, there can.
- tom-lord 12y agoThe point is that if there is a prime factor greater than sqrt(n), then your will have already found its co-factor by then.
- jdmichal 12y agoCorrect. I misspoke. I should have said, A better implementation will only check to sqrt(n), as there can be no prime factor greater than that without there also being a prime factor lower than that.