Project Euler Problem 21.

The task:

http://projecteuler.net/problem=21

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a !=  b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284.
The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.

So it's pretty easy task but with a hint - fast divisors calculation.

import time

def amicable_pairs_fast(n):

    div_sum = [1]*n
    for i in range(2, int(n/2) + 1):
        for j in range(i, n, i):
            if j != i:
                div_sum[j] += i
    total = 0
    for i in range(1, n):
        s = div_sum[i]
        if s < n:
           s1 = div_sum[s]
           if  s1 == i and s != i:
              total += s1
    return total

t1 = time.time()
print("%d " % amicable_pairs_fast(10000) + " Time (s): %f " % (time.time()-t1))

Here is the timing for different languages for the 10 000 000 testcase:

amicible pairs less than 10 000 000
-----------------------------------
g++       :  4.32 sec.
Java 1.7  :  4.36 sec.
C# 4      :  4.45 sec.
pypy 1.9  :  5.29 sec. (!!!)
python 2.7: 36.09 sec.