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:
public void findDivisors(BigInteger num){
BigInteger limit = num;
BigInteger counter = BigInteger.ONE;
while(counter.compareTo(limit) < 0)
{
if (num.mod(counter).compareTo(BigInteger.ZERO) == 0)
{
emit(counter);
BigInteger partner = num.divide(counter);
emit(partner);
limit = partner; // shorten the loop
}
counter = counter.add(BigInteger.ONE);
}
}
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:
public void findDivisors(BigInteger num){
BigInteger limit = num;
BigInteger counter = BigInteger.ONE;
while(counter.compareTo(limit) < 0)
{
if (num.mod(counter).compareTo(BigInteger.ZERO) == 0)
{
emit(counter);
BigInteger partner = num.divide(counter);
emit(partner);
limit = partner; // shorten the loop
}
counter = counter.add(BigInteger.ONE);
}
}
It starts counting up from 1 to N, looking for divisors, integers that divide into the original BigInteger with no remainder. Every time it finds an integer divisor, it calculates its partner. It then reduces the number of iterations by moving up the loop's limit end-point to the partner value.
(In the above code, I call a method emit() to do something with any found divisors, such as printing them to console or adding them to a collection. Ignore those lines if they distract from the algorithm itself.)
The number of times through the loop in this approach converges on the square-root point, always exceeding it by a small margin of course.
Results:
Using 10! (3,628,800), which has a square root of 1,904.94, my algorithm iterates 1,920 times. Those 15 extra iterations are an increase of 0.79% compared to using the square-root as the limit.
Using 15! (5811886080), which has a square root of 76,235.73, my algorithm iterates 76,440 times. Those 204 extra iterations are an increase of 0.27% compared to using the square-root as the limit.