Project Euler Problem 12 in Python I'm trying to do Project Euler Problem 12, which reads as:


  The sequence of triangle numbers is generated by adding the natural
  numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7
  = 28. The first ten terms would be:
  
  1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
  
  Let us list the factors of the first seven triangle numbers:
  
  1: 1
  
  3: 1,3
  
  6: 1,2,3,6
  
  10: 1,2,5,10
  
  15: 1,3,5,15
  
  21: 1,3,7,21
  
  28: 1,2,4,7,14,28
  
  We can see that 28 is the first triangle number to have over five
  divisors.
  
  What is the value of the first triangle number to have over five
  hundred divisors?


My code is as follows:

import math
from time import time
t = time()
def divisors(n):
    number_of_factors = 0
    for i in range(1, int(math.ceil(math.sqrt(n)))):
        if n % i == 0:
            number_of_factors +=2
        else:
            continue
    return number_of_factors

x=1
for y in range(2,1000000):
    x += y
    if divisors(x) &gt;= 500:
        print x
        break
tt = time()-t
print tt


My code takes 3.8 seconds to run, and I know this can be done in around 0.2 seconds in Java. Any suggestions on how to make this run faster?
Improving project Euler solutions is usually done by improving the algorithms itself rather than just optimising the code.

First things first, your divisors() function is wrong and does not work for perfect squares.  To fix this, you need to take care of the sqrt(n) case separately:

def divisors(n):
    number_of_factors = 0
    for i in xrange(1, int(math.ceil(math.sqrt(n)))+1):
        if n % i == 0:
            number_of_factors +=2
        if i*i==n:
            number_of_factors -=1
    return number_of_factors


Now we come to the main part of the code. The important observation to improve your code is that the nth triangular number is given by T(n) = n(n+1)/2. Now, n and n+1 are coprime. If a and b are coprime numbers, the number of divisors of a*b is just the product of number of divisors of a and b.

This suggests the following improvement for the main part of the code:

for n in xrange(1,1000000):
    Tn=(n*(n+1))/2
    if n%2==0:
        cnt=divisors(n/2)*divisors(n+1)
    else:
        cnt=divisors(n)*divisors((n+1)/2)
    if cnt &gt;= 500:
        print Tn
        break


The improvement this provides is very significant. You can improve the performance further by modifying the divisor function to use the same technique:

def divisors(n,start):
    if n==1:
        return 1
    for i in xrange(st, int(math.ceil(math.sqrt(n)))+1):
        if n % i == 0:
            cnt=1
            while(n%i==0):
                n/=i
                cnt+=1
            return divisors(n,i+1)*cnt
    return 2


Essentially, we find p, the first prime factor of n. If p^k is the maximum power of p that divides n, (k+1)*divisors(n/p^k) is the number of divisors of n. start is just a starting point for checking prime divisors.

Overall, these modifications seem to reduce running time from ~5s to 0.15s on my laptop.