/**
 * Highly divisible triangular number
 *
 * 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?
 *
 * https://projecteuler.net/problem=12
 */

fun main() {
    println(highlyDivisibleTriangularNumber(5))
    println(highlyDivisibleTriangularNumber(500))
}

private fun highlyDivisibleTriangularNumber(n: Int): Int {
    var num = 1
    while (true) {
        val triangular = (num * (num + 1)) / 2
        val numberOfFactors = primeFactorizationOf(triangular)
            .map { it.value + 1 }
            .fold(1L) { acc, i -> acc * i }

        if (numberOfFactors > n) {
            return triangular
        }

        num++
    }
}

fun primeFactorizationOf(n: Int): Map<Int, Int> = buildMap {
    var num = n
    while (num != 1) {
        primeLoop@ for (i in 1..n) {
            if (primes[i] == 0) {
                primes[i] = findPrime(i).toInt()
            }
            val prime = primes[i]
            if (num % prime == 0) {
                num /= prime
                set(prime, getOrDefault(prime, 0) + 1)
                break@primeLoop
            }
        }
    }
}

private val primes = IntArray(65500) { 0 }
