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.

### Like this:

Like Loading...