from timeit import default_timer


# ===========================================================
# FUNCTION: get_prime_factors
# ===========================================================
#
#  Input: integer n to find the largest prime factor of
#
#  Output: the largest prime number that divides n
#
#  Task:    iterate through integers <= sqrt(n), checking if
#           that integer divides n. this continues until all
#           integers that divide n have been accounted for,
#           and returns that integer
#
# ===========================================================
def get_prime_factors( n ):
    # Set Up Variables
    i        =  2
    factors  =  [ ]

    # Main Computation Loop, no number has a factor > its square-root
    while i * i <= n:
        # If i is not a factor of n, increment i
        if n % i is not 0:
            i  +=  1

        # Otherwise, divide i from n and record i as a factor
        else:
            n  //=  i
            factors.append( i )

        continue  # close while i*i<=n (added for readability)

    # Ensure that all factors have truly been removed
    if n > 1:
        factors.append( n )

    # Return list of all factors of n
    return factors


# ===========================================================
# PROBLEM 12 -- Highly Divisible Triangular Number
# ===========================================================
#
#  The sequence of trianglular 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
#
# ===========================================================
#
# method to compute factor count:
#    1. Find the prime factors
#    2. take the exponents and add one to each
#    3. multiply the product of the new exponents
#
#    i.e.
#       1. prime factors of 72 = 2^3 * 3^2
#       2. incremented powers = 4 and 3
#       3. product of these new powers = 4*3 = 12
#       Therefore 72 has 12 factors
#       [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
#
# Note:
#   this behavior of prime factor powers was obtained from
#   https://www.hitbullseye.com/Quant/Factors-Number.php
#
# ===========================================================
def problem_12( ):
    # Print Problem Context
    print( "Project Euler Problem 12 -- Highly Divisible Triangular Number" )

    # Set Up Variables
    start_time  =  default_timer( )
    n           =  500 * 2

    # Loop will manually be broken-out of
    while True:
        # Compute nth triangle number using closed-form-formula, then retrieve its factors
        t             =  ( n * ( n + 1 ) ) // 2
        primeFactors  =  get_prime_factors( t )
        tally         =  1

        # Using the method specified above, determine number of proper divisors from prime factors
        for x in set( primeFactors ):
            tally  *=  ( primeFactors.count( x ) + 1 )
            continue  # for x (added for readability)

        # Condition for result to be found
        if tally > 500:
            break

        # Increment to the next triangle number
        n  +=  1
        continue  # While True

    # Compute Execution Time
    end_time        =  default_timer( )
    execution_time  =  ( end_time - start_time ) * 1000

    # Display Result
    print( "   Triangle Number x with over 500 factors:   %d"     % t )
    print( "   Computation Time:                          %.3fms" % execution_time )
    return


if __name__ == '__main__':
    problem_12( )