Problem Analysis
This problem revolves around the divisor function, specifically the sum of proper divisors of a number n - the positive integers strictly less than n that divide n evenly. We call this d(n). Two distinct numbers a and b form an amicable pair when d(a) = b and d(b) = a. The task is to sum every number under 10,000 that participates in such a pair. The crucial observation is that we do not need to search for pairs directly: for each candidate x we compute y = d(x), then check whether d(y) = x and y differs from x. If so, x is amicable. The condition y != x is what excludes perfect numbers, where d(n) = n - these are not amicable because the definition demands two distinct numbers.
The efficiency hinges on how we compute d(n). A naive approach tests every integer from 1 to n-1, costing O(n) per number. Instead I enumerate divisors in pairs: every divisor i below the square root of n has a matching co-divisor n/i above it. By iterating only from 2 to floor(sqrt(n)) and harvesting both i and n/i whenever i divides n, the cost per number drops to O(sqrt(n)). The single subtlety is a perfect square, where sqrt(n) pairs with itself and would be counted twice - so I subtract it once. Across all numbers up to a limit N, the total work is O(N * sqrt(N)), which for N = 10,000 is roughly one million operations - trivial for a modern machine.
Solution Approach
Trial Division with Divisor Pairing (Python and C)
The Python solution (p0021_s0.py) and the C solution (p0021_s0.c) implement the same algorithm in two languages. The heart of both is sum_factors(n), which computes d(n). I initialise the running total to 1, since 1 is a proper divisor of every n greater than 1. I then loop i from 2 up to n_sqrt = floor(sqrt(n)); whenever n % i == 0, I add both i and n/i to the total. Finally, if n_sqrt * n_sqrt == n, the number is a perfect square and its square root was added twice (once as i, once as n/i), so I subtract it once. This formulation is correct by construction and avoids any conditional inside the hot loop other than the divisibility test.
The main loop walks x from 2 to max_num inclusive. For each x, it evaluates y = sum_factors(x), then accepts x as amicable when both y != x and sum_factors(y) == x. I deliberately placed the inexpensive comparison y != x first so that the more expensive second divisor-sum call is short-circuited whenever x is a perfect number or self-mapping. I do not constrain y to lie within max_num, because an amicable partner can legitimately fall outside the search window while the number itself is inside it - the membership condition is on x, not on its partner.
The Python version memoises sum_factors with functools.lru_cache, but defines the helper inside solve() rather than at module scope, so the cache is rebuilt on every call. This is a deliberate benchmarking choice: the harness invokes solve() many times in one process to average its runtime, and a module-level cache would survive between those runs - the first run would pay the full cost and every later run would read cached answers, reporting a falsely low time. A per-call cache is discarded and rebuilt each run, so the recorded average reflects the true cost of one solve. The C version omits memoisation entirely because C offers no built-in equivalent and the problem is small enough that recomputation is cheap. The benchmark bears this out: C runs in about 1.6 ms while Python takes about 22 ms, a roughly 14x gap driven mainly by interpreter overhead rather than the caching difference.