Project Euler-Problem #12

PythonEuler12.py

from itertools import groupby
from collections import defaultdict

def divides(k,n):
	"""
	Determines if number n is divisible by n
	"""
	return n % k == 0

def ldf(n, k):
	"""
	Obtains the least divisor of n starting from k.
	"""
	while True:
		if divides(k, n): 
			return k
		elif k ** 2 > n:
			return n
		else:
			k += 1

def ld(n):
	"""
	Obtains the least divisor of n starting from 2.
	"""
	return ldf(n, 2)


def count_factors(n):
	"""
	Counts the number of factors of n based on the exponents of the
	prime factors of n.
	"""
	groups = defaultdict(int)
	while(n > 1):
		factor = ld(n)
		groups[factor] += 1
		n = n / factor
	return reduce(lambda a, b: a * b, map(lambda x: x + 1, groups.values()))
	
def calc_triangle(n):
	"""
	Calculates the triangle number of n.
	"""
	return n * (n + 1) / 2

def solve():
	n = 2
	while True:
		triangle = calc_triangle(n)
		count = count_factors(triangle)
		if count > 500:
			return triangle
		n += 1

print "The first triangle number to have over 500 factors is: %d" % solve()