Project Euler Problem 21 in Python: Summing amicable numbers 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.


My solution to the 21 problem on project Euler is very slow (with pure brute force it took 30 mins to find the solution). Any ways that I can improve my code or should I scrap it and think about something else ?

Here's my code :

import time, math

start = time.time()

amicable_nums = set()

def sum_div(n):
    divisors = []
    for x in range(1, int(math.sqrt(n) + 1)):
        if n % x == 0:
            divisors.append(x)

            if x * x != n and x != 1:
                divisors.append(int(n / x))
    return sum(divisors)

for i in range(1, 10000):
    for j in range(1, 10000):
        if sum_div(i) == j and sum_div(j) == i and i != j:
            amicable_nums.update([i, j])

print(sum(amicable_nums))
print("It took " + str(time.time() - start) + " seconds")
In your sum_div method, 1 is always a divisor, and n/1 is never a “proper” divisor of n.  So you can remove the “1” case from your loop, and get rid of the x != 1 test, for a slight speed increase. 

Also, if n % x == 0, then the other divisor is n // x; no call to int() is required. 

Finally, no list creation is required.  Just maintain a running total. 

def sum_div(n):
    total = 1
    for x in range(2, int(math.sqrt(n) + 1)):
        if n % x == 0:
            total += x
            y = n // x
            if y &gt; x:
                total += y
    return total




In your main loop, your search for i,j both in range(1,10000), and add both i, j (if different) to your set to ensure you don’t have duplicates. 

You can cut down your search space by half by recognizing that if you find one pair i, j, you have also found the other pair j, i, and adding the other pair to the set is a no-op.  You only need to search the cases where (say) i &lt; j is true, which eliminates just over half of the pairs. 

for i in range(1, 10000):
    for j in range(i+1, 10000):
        if sum_div(i) == j and sum_div(j) == i:
            amicable_nums.update([i, j])




How many times are you computing sum_div(i)???  Does it change in the inner loop?  Maybe you could only compute it once per loop?

for i in range(1, 10000):
    sdi = sum_div(i)
    for j in range(i+1, 10000):
        if sdi == j and sum_div(j) == i:
            amicable_nums.update([i, j])




Do you really need the inner loop?  sdi == j will only be true for exactly one value in the loop.