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

primes_under_100 = [2,3,5,7,11,13,17,19,23,29,31,37,41,
                    43,47,53,59,61,67,71,73,79,83,89,97]
def is_prime(n):
    if n == 2 or n == 3: return True
    if n < 2 or not n%2: return False
    if n < 9: return True
    if not n%3: return False
    r = int(n**0.5)
    f = 5
    while f <= r:
        if not n%f: return False
        if not n%(f+2): return False
        f +=6
    return True

def primes_upto(n, start=3, calc=False):
    if calc:
        if n > 2: yield 2
        for x in range(start, n, 2):
            if is_prime(x): yield x
    else:
        if n < 100:
            for p in primes_under_100:
                if p < n: yield p
        else:
            if n > 2: yield 2
            for x in range(start, n, 2):
                if is_prime(x): yield x

def triangle_numbers(ceiling, start=1):
    x = 0
    if start == 1: yield 1
    for i in range(1, ceiling+1):
        x+=i
        if start < i: yield x

def prime_factors(n):
    # primes = primes_upto(n//2)
    factors = [ ]
    for d in primes_under_100:
        if not n%d: #divisable
            n //= d
            factors.append(d)
            while not n%d:
                n //= d
                factors.append(d)
    return factors

def number_of_divisors(n):
    factors = prime_factors(n)
    num = 1
    for i in list(set(factors)):
        num *= factors.count(i) + 1
    return num

def main():
    largest = 0
    for i, x in enumerate(triangle_numbers(100000), start=1):
        n = number_of_divisors(x)
        # print(f'\ti{i}\tx{x}\tn{n}')
        if largest < n:
            largest = n
            print(i, largest)
        if n > 500:
            print(f'OVER 500: num={x}, divs={n}, i={i}')
            break

if __name__ == '__main__':
    main()