Return to Revisions

Another way to speed this up is to keep a record of all the sum of divisors seen so far (by using a caching decorator on the function, like functools.lru_cache) 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

print(sum(amicable_numbers(10000)))
    

This runs in a bit more than 4 milli-seconds on my computer.

As for timing the runtime, I usually either prefer using ipythons magic command %timeit, or writing a small context manager:

from time import perf_counter

class Timer:
    def __init__(self, name=""):
        self.name = name

    def __enter__(self):
        self.start = perf_counter()

    def __exit__(self, *args):
        runtime = perf_counter() - self.start

        # get it in nice units
        units = ["s", "ms", "μs"]
        for unit in units:
            if runtime > 1:
                break
            runtime *= 1000

        if self.name:
            print(f"{self.name}: {runtime:.1f}{unit}")
        else:
            print(f"{runtime:.1f}{unit}")

Which you can use like this:

with Timer("amicable numbers"):
    print(sum(set(amicable_numbers(10000))))
# XXXXX  # I don't want to give away the correct answer
# amicable numbers: 4.1ms

Note that this will not be more precise than micro-seconds due to the time it takes to run the context manager.