I was working on one of the math programming challenges from Project Euler recently and needed to implement an algorithm to find all of the divisors of a BigInteger. A bad brute-force approach would be to visit all values from 1 to N and see which ones divide evenly into N. A better approach would be to just check all values from 1 to the square root of N. Any values found that divide evenly into N will also give another divisor, since if we have value i then we can find j = N / i where i <= j But the Java API for BigInteger does not include a calculation of its square root. And I don't want to write an algorithm to calculate the square root today. This algorithm, however, is almost as efficient as one limited by the square root:
Musings on Tests, Quality, Tools, Projects and more. By Steve Page