Calculating the first triangle number to have over 500 divisors in python
math, performance, python
Solution
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 `n`th 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.
Problem
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) ```