Let
be defined as the sum of proper divisors of
(numbers less than
which divide evenly into
).
If
and
,
where
,
then
and
are an amicable pair and each of
and
are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44,
55 and 110; therefore
.
The proper divisors of 284 are 1, 2,
4, 71 and 142; so
.
Evaluate the sum of all the amicable numbers under 10000.
The two non-trivial parts of this problem involve getting the prime factors
of a number and, based on that, finding all factors of that number.
To find the prime factors I just divide out progressively higher prime numbers
using loops. To find all factors I multiply the prime factors with each other.
Once I have these two algorithms in place, I can iterate through the numbers,
looking for amicable pairs. When I find them, I add them to an array and
sum them.
###,###