In the first part we discussed how to compute the sum of proper divisors function
from the sum of divisors function,
. We saw that if we factorize the number
then compute the list divisors from prime factor, it was much faster (on average) than testing each possible numbers from
to
(or
, since we get one large divisor for every small divisors).

So now, let’s all put that together to get an efficient program that enumerates amicable pairs. First, we obtain a list of primes (not missing any) where the largest prime is
, the largest number we will be testing—we need it to compute (up to)
. If we were to search for all amicable numbers, the list would need to be unbounded, maybe we would need to produce it as we go along; but if we look for amicable pairs up to, say, about
, we only need primes up to
(and there’sn’t that many of them). For the sake of efficiency, we also need a way of not testing a number twice.
Read the rest of this entry »