Project Euler 21: Sum of amicable numbers optimisation 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.


I have the following code which I know works, but is very slow for large numbers.

import time
start = time.time()

n = int(input("Enter a number"))


def factor(c):
    factors = []
    for d in range(1, int(c / 2) + 1):
        if c % d == 0:
            factors.append(d)
    return sum(factors)


def sum_ammicable(x):
    ammicable = set()
    for a in range(1, x):
        for b in range(1, x):
            if a != b:
                if factor(a) == b and factor(b) == a:
                    ammicable.update([a,b])
    return sum(ammicable)


print(sum_ammicable(n))

end = time.time()
print(end -start)


How can I optimise this code
Integer Division

Python comes with a built-in integer division operator.  So instead of writing int(c / 2) + 1, you could simply write c // 2 + 1.  It is slightly faster.

Unnecessary List Creation

Creating a list of factors just to sum(factors) afterwards is unnecessary busy work, which takes time.  Simply add up the factors as you find them:

def factor(c):
    total = 0
    for d in range(1, c // 2 + 1):
        if c % d == 0:
            total += d
    return total


Or, use a generator expression with sum():

def factor(c):
    return sum(d for d in range(1, c // 2 + 1) if c % d == 0)


There is no need to store the factors you found.

Move Invariants out of Loops

Consider:

def sum_ammicable(x):
    ...
    for a in range(1, x):
        for b in range(1, x):
            if a != b:
                if factor(a) == b and ...:
                    ...
    ...


How many times is factor(a) computed when a==1?  If x == 10000, it gets computed 10000 times ... once for each b value.  How many times when a==2?  It'll get computed 10000 times as well.  But does factor(a) depend on the value of b?  No.  Each time you compute factor(a), for the same value of a, the same result is produced.

Can you calculate this value once per a loop?  Sure!  Move it out of the b loop!

def sum_ammicable(x):
    ...
    for a in range(1, x):
        factor_a = factor(a)
        for b in range(1, x):
            if a != b:
                if factor_a == b and ...:
                    ...
    ...


Instead of computing factor(a) 100,000,000 times, you now only compute it 10,000 times, which should be a significant improvement in speed.

Finally, considering that:

        for b in range(1, x):
            ...
                if factor_a == b and ...:
                    ...


will only execute the rest of the if statement (and perhaps the body of the if) for exactly one value of b, do you really need to loop over all 10,000 possible b values?  With a little thought, and a little reworking of the code, you can remove the b loop altogether!

Group Related Code Together

You start with 

start = time.time()

n = int(input("Enter a number"))


then 2 function definitions, and then you continue with mainline code:

print(sum_ammicable(n))

end = time.time()
print(end -start)


Move the code together, after the function declarations.  Even better, place it inside a if __name__ == '__main__': guard, so you can import factor(c) and sum_ammicable(x) functions into other code:

if __name__ == '__main__':

    start = time.time()

    n = int(input("Enter a number"))

    print(sum_ammicable(n))

    end = time.time()
    print(end - start)


Now that this code isn't separated by 2 functions, it becomes apparent you are timing how long the user takes to "Enter a number" in addition to the time it takes to compute sum_ammicable(n).  Is the user's reaction &amp; typing speed really being profiled here?  Perhaps you want to move start = time.time() after the input statement.

Pro tip: use time.perf_counter() instead of time.time() for higher accuracy profiling.



Algorithmic improvements are covered on the Project Euler site itself.  Read the problem overview after successfully completing the problem for some additional dramatic improvements.  There is no need to reproduce their analysis here.