import sys
import math
import time
# 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?


def factorisation(number):
        num = [number]

        # prime factorisation
        # add 2 to list or prime factors and remove all even numbers(like sieve of ertosthenes)
        while number % 2 == 0:
            num.append(2)
            number //= 2

        # divide by odd numbers and remove all of their multiples increment by 2 if no perfectlly devides add it
        for i in range(3, int(math.sqrt(number)) + 1, 2):
            while number % i == 0:
                num.append(i)
                number //= i

        if number > 2:
            num.append(number)
        num.append(1)
        num.sort()

        for i in range(1, len(num) - 1):
            for g in range(i + 1, len(num)):
                if num[g] % num[i] == 0:
                    if num[g] == num[i]:
                        num[g] = num[g] * num[i]
                if num[len(num) - 1] % (num[i] * num[g]) == 0 and num[i] * num[g] < num[len(num) - 1]:
                    num.insert(len(num) - 1, num[i] * num[g])

        num = list(set(num))

        return num


def divisorcheck(morethan):
    divisors = []
    triangular = 0
    for i in range(1, sys.maxsize):
        triangular = i * (i + 1) // 2      # get triangular number
        divisors = factorisation(triangular)
        if len(divisors) > morethan:
            break

    return triangular


inp = 500
# print(factorisation(76576500))
start_time = time.time()
print(divisorcheck(inp))
print("--- %s seconds ---" % (time.time() - start_time))
