#!/usr/bin/env python
#-*-coding:utf-8-*-

'''
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 timeit
import math

# very slow
def loop(n):
    c = 1 # count
    t = 0 # triangle number
    while True:
        t += c
        d = get_divisor(t)
        if d >= n:
            return t
        else:
            c += 1

# faster
# http://tsumuji.cocolog-nifty.com/tsumuji/2010/01/project-euler-2.html
def factorize(n):
    c = 1
    p = 1
    while True:
        p_next = get_divisor((c+1)/2) if (c+1) % 2 == 0 else get_divisor(c+1)
        if p*p_next > n:
            return c*(c+1)/2
        else:
            c += 1
            p = p_next

def get_divisor(n):
    d = 0
    for i in range(1, int(math.sqrt(n)+1)):
        if i*i == n:
            d += 1
        elif n % i == 0:
            d += 2
    return d

if __name__ == '__main__':
    print loop(500)
    print factorize(500)
    print timeit.Timer('problem_012.loop(500)', 'import problem_012').timeit(1)
    print timeit.Timer('problem_012.factorize(500)', 'import problem_012').timeit(1)

add problem 12