performance - Calculating the first triangle number to have over 500 divisors in python

Question

I'm trying to solve the 12th problem on Project Euler. I can calculate the number that has over 500 divisors in almost 4 minutes. How can i make it faster? Here's the attempt;

import time

def main():
    memo={0:0,1:1}
    i=2
    n=200
    while(1):
        if len(getD(getT(i)))>n:
            break
        i+=1
    print(getT(i))

#returns the nth triangle number
def getT(n):
    if not n in memo:
        memo[n]=n+getT(n-1)
    return memo[n]

#returns the list of the divisors
def getD(n):
    divisors=[n]
    for i in xrange(1,int((n/2)+1)):
        if (n/float(i))%1==0:
            divisors.append(i)
    return divisors

startTime=time.time()
main()
print(time.time()-startTime)

Answer 1

You don't need an array to store the triangle numbers. You can use a single int because you are checking only one value. Also, it might help to use the triangle number formula:n*(n+1)/2 where you find the nth triangle number.

getD also only needs to return a single number, as you are just looking for 500 divisors, not the values of the divisors.

However, your real problem lies in the n/2 in the for loop. By checking factor pairs, you can use sqrt(n). So only check values up to sqrt(n). If you check up to n/2, you get a very large number of wasted tests (in the millions).

So you want to do the following (n is the integer to find number of divisors of, d is possible divisor):

• make sure n/d has no remainder.
• determine whether to add 1 or 2 to your number of divisors.