Another way to speed this up is to keep a record of all the sum of divisors seen so far in a dictionary (by using a caching decorator on the function, like [functools.lru_cache
][1]) and realize that you only need a single loop if you make this a generator and use the fact that a number is amicable if \$d(d(a)) = a\$ and \$d(a) \neq a\$:
import math
from functools import lru_cache
@lru_cache(None)
def sum_div(n):
# Taken from AJNeufeld's answer
total = 1
for x in range(2, int(math.sqrt(n) + 1)):
if n % x == 0:
total += x
y = n // x
if y > x:
total += y
return total
def amicable_numbers(limit):
for a in range(limit):
b = sum_div(a)
if a != b and sum_div(b) == a:
yield a
yield b
print(sum(set(amicable_numbers(10000)))) # need `set` to avoid double counting
This runs in a bit more than 3 milli-seconds on my computer.
Here I used a set
to avoid double counting, but I also could have used the fact that amicable numbers always come in pairs by definition and divided the sum by two. But this could have run afoul if one half of the pair is above the limit
. In other words, for limit = 250
it would have yielded the wrong result.
[1]: https://docs.python.org/3/library/functools.html#functools.lru_cache