We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #12: Highly divisible triangular number
  4. Discussions

Project Euler #12: Highly divisible triangular number

  • muchomichael1
     + 0 comments

    Pefect Solution In Python You can use the property that the number of divisors of a triangle number T_n = n*(n+1)//2 is the product of the number of divisors of n//2 and n+1 (if n is even), or n and (n+1)//2 (if n is odd). This allows you to factorize smaller numbers and reuse results.

    def count_divisors(n):
    cnt = 1
    i = 2
    while i * i <= n:
        power = 0
        while n % i == 0:
            n //= i
            power += 1
        cnt *= (power + 1)
        i += 1
    if n > 1:
        cnt *= 2
    return cnt

def first_triangle_with_divisors(limit):
    n = 1
    while True:
        if n % 2 == 0:
            a = n // 2
            b = n + 1
        else:
            a = n
            b = (n + 1) // 2
        divisors = count_divisors(a) * count_divisors(b)
        if divisors > limit:
            return n * (n + 1) // 2
        n += 1

T = int(input())
Ns = [int(input()) for _ in range(T)]
for N in Ns:
    print(first_triangle_with_divisors(N))