'''
Project Euler Problem #12

The sequence of triangle numbers is generated by adding the natural numbers.
ex) the 7th triangle number would be 1 + 2 + 3 + ... + 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?
'''

from functools import reduce
import operator
from time import time

# Approach:
# find the number of factors in the given triangle number
# -> find prime factorization
# -> add 1 to exponents & multiply the exponents

# how to find prime factorization?
# -> find primes then divide

# Using the prime_number generator from Problem 10...
def isPrime(n):
    if n == 1:
        return False
    elif n in [2, 3]:
        return True
    for d in range(2, int(pow(n, 1/2)) + 1):
        if n % d == 0:
            return False
    return True

def prime_number_generator():
    n = 3
    yield 2
    yield 3
    while True:
        n += 2
        if isPrime(n):
            yield n

def triangle_number_generator():
    n = 0
    offset = 1
    while True:
        n += offset
        offset += 1
        yield n

def primeFactorization(n):
    '''
    input: n, int
    output: list of (a,b) sets
    desc: find prime factorization of n
    '''
    if n == 1: return [(1,1)]
    p_gen = prime_number_generator()
    pf = []
    p = next(p_gen)
    while n != 1: # add prime test
        exp = 0
        while n % p == 0:
            exp += 1
            n = n // p
        if exp != 0:
            pf.append((p, exp))
        p = next(p_gen)
    return pf

def numberOfFactors(pf):
    '''
    input: prime factorization of n, list of (a,b) sets
    output: number of factors, int
    desc: exponents + 1 and multiply all exponents to get number of factors
    '''
    return reduce(operator.mul, [exp+1 for p, exp in pf])


def stringify(pf):
    s = ''
    for p,exp in pf:
        s += str(p) + '^' + str(exp) + ('*' if (p,exp) != pf[-1] else '')
    return s

def try1():
    gen = triangle_number_generator()
    while True:
        n = next(gen)
        pf = primeFactorization(n)
        nf = numberOfFactors(pf)
        if nf > 500:
            print(n,':', stringify(pf), '# of factors:', nf)
            break

def try2():
    '''
    different approach by 코딩허접
    This approach utilizes the fact that factors come in pairs.
    '''
    number = 1
    add = 2
    count = 0
    while True:
        t_number = int(number**0.5)
        if t_number == number**0.5:
            count+=1
        for i in range(1, t_number+1):
            if number%i == 0:
                count+=2 
        if count >= 500:
            print("%d: %d"%(number, count))
            break
        number += add
        add += 1
        count = 0

def timer(f):
    start = time()
    f()
    end = time() - start 
    print(f, '-- %s seconds --' % round(end, 2))

if __name__ == '__main__':
    timer(try1) 
    timer(try2)
