from math import sqrt

sum1to = __import__("001 - sum multiples of 3 and 5").sum1to
factorize = __import__("003 - largest prime factor of composite").factorize

def num_factors(n):
    """num_factors(int) -> int

    Return the number of factors (prime or not) for a given number.
    """
    factors = factorize(n)
    num = 1
    for x, exp in factors:
        num *= (exp+1)
    return num

def triangle_with_min_num_factors_slow(min_num_factors):
    i = 1
    factor_count = 1
    num = 1

    while factor_count < min_num_factors:
        i = i+1
        num = sum1to(i)
        factor_count = num_factors(num)
    else:
        triangle_number = sum1to(i)
        return i, num, factor_count

    return 0, 0, 0

def triangle_with_min_num_factors_slower(min_num_factors):
    i = 0
    num = 0

    while True:
        i = i+1
        num += i
        num_factors = 0

        n = 1
        root = int(round(sqrt(num)))

        while n <= root:
            if (num % n) is 0:
                num_factors += 2
            n += 1

        if num_factors >= min_num_factors:
            return i, num, num_factors

    return 0, 0, 0

if __name__ == "__main__":
    num, triangle, num_factors = triangle_with_min_num_factors_slow(500)

    print """First triangle number with >= 500 factors is triangle(%d)=%d
    %d has %d factors.""" % (num, triangle, triangle, num_factors)