Counting Divisors

A little over a year ago I started working on Project Euler problems. Used them as a handy way of learning Python. About that time I ran into a problem that stumped me completely. Problem 12 wanted to know the first triangle number with more than 500 divisors.

A triangle number of order (n) is defined as the sum of the arithmetic sequence from 1 to n, so triangle(3)=1+2+3=6 and triangle(7)=1+2+3+4+5+6+7=28. Calculating a triangle number is trivial. Figuring out how many divisors it has is a bit more challenging. I was trying various things that first time with caching the number of divisors for various numbers as you go up so that you don't have to calculate it again. Honestly, I don't really remember exactly what I did, but I remember that it was big and it took far more than the 1 minute maximum that any Project Euler problem should take. It took so long that I didn't even have the patience to let it run until it found a solution.

I skipped the problem then and let it sit undone for a long time. Until today. I fired up my trusty editor and busted out a solution. And it worked. And I'm thrilled. Not least because the code I came up with for finding the divisor takes all of 4 lines and only breaks the 1 second execution time mark at around n=1e+13 . Here's the code:

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

This works for n greater than 1.