Skip to main content
1 of 4
Graipher
  • 41.1k
  • 7
  • 69
  • 133

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

Graipher
  • 41.1k
  • 7
  • 69
  • 133