Task_12_Highly_Divisible_Triangular_Number.py

"""
https://projecteuler.net/problem=12
The sequence of triangle numbers is generated by adding the natural numbers.

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?

"""

GOAL = 500


def triangle_numbers():
    idx = 1
    while True:
        yield int(idx * (idx + 1) / 2)
        idx += 1


def find_prime_numbers(n):
    d = 2
    numbers = []
    while n > 1:
        if n % d == 0:
            n = n / d
            numbers.append(d)
            d = 2
            continue
        d += 1

    return numbers


if __name__ == "__main__":
    for number in triangle_numbers():
        if number == 1:
            continue

        prime_numbers = find_prime_numbers(number)
        prime_numbers_with_powers = {}
        for p in prime_numbers:
            if p not in prime_numbers_with_powers:
                prime_numbers_with_powers[p] = 1
                continue
            prime_numbers_with_powers[p] += 1

        dividers_power = [n + 1 for n in prime_numbers_with_powers.values()]
        dividers_count = dividers_power[0]
        for p in dividers_power[1:]:
            dividers_count *= p

        if dividers_count > GOAL:
            print(number)
            break

# the answer is 76576500