Back at amicable numbers.

My first solution using two nested for-loops was obviously way too slow. But how to improve? I did some reading on the Project Euler forum therefore.

The nested for-loops are gone, only a single loop remains. Also, as I am only interested in the amicable numbers’ sum, it is time to kick out the totally unnecessary ArrayList.

For every number k between 2 and 9.999 I calculate the sum of its proper divisors j. Only in case j is larger than the input k, I calculate the sum of proper divisors for j as well. And compare it back to k.

If you think about it for a second, the check if (j > k) {…} is kind of obvious. A pair of amicable numbers always consists of a smaller and a larger number. My for-loop runs from 2 to 9.999, I will always “find” the smaller number first. The sum of its proper divisors has to be the larger number therefore.

This improvement causes a dramatic increase in execution speed. 10 minutes down to an instant result!

It looks like my function sumOfProperDivisors(int num) can be improved as well. This will become “Project Euler – Amicable numbers (Part 4)”, most likely my final post about this topic.