Project Euler Problem #12 - Highly Divisible Triangular Number (in Python)

The main concept of this algorithm is decreasing the time it takes to complete. Using brute force (checking all numbers from 1 to n, or even 1 to n/2) will absolutely not work. Your program will not finish.

What I've done is only checked numbers from 1 to sqrt(n), which helps an incredible amount. In fact, it reduces the time to about 50 seconds (although, it takes less than a second in Java - take a look here). To put the restriction of the square root of the number into perspective, let's say we were dealing with a number that was 2 million (close to the actual answer). The square root of 2 million is about 1400, which means instead of 2 million iterations, we only have a thousand. That compounded to every number that's being tested saves an incredible amount of iterations, and therefore, time.

All of the factors from 1 to the square root of a number contain exactly one half of all the factors of that number. So, you only need to test from 1 to sqrt(n) and then multiply that result by 2 to count the other corresponding half of the factors.

All of the factors that are less than the square root of the number directly correspond to the other half of the factors. That means that a factor from the first half has to be multiplied by its corresponding factor from the second half to result in the final number.

# 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?


import time

# returns the nth triangle number; that is, the sum of all the natural numbers less than, or equal to, n
def triangleNumber(n):
    return sum ( [ i for i in range(1, n + 1) ] )

start = int(round(time.time() * 1000)) # starts the stopwatch

j = 0 # j represents the jth triangle number
n = 0 # n represents the triangle number corresponding to j
numberOfDivisors = 0 # number of divisors for triangle number n

while numberOfDivisors <= 500:

    # resets numberOfDivisors because it's now checking a new triangle number
    # and also sets n to be the next triangle number
    numberOfDivisors = 0
    j += 1
    n = triangleNumber(j)

    # for every number from 1 to the square root of this triangle number,
    # count the number of divisors
    i = 1
    while i <= n**0.5:
        if n % i == 0:
            numberOfDivisors += 1
        i += 1

    # 1 to the square root of the number holds exactly half of the divisors
    # so multiply it by 2 to include the other corresponding half
    numberOfDivisors *= 2

finish = int(round(time.time() * 1000)) # stops the stopwatch

print (n)
print ("Time taken: " + str(finish-start) + " milliseconds")

          Created: March 7, 2014
Completed in full by: Michael Yaworski