如何在Kotlin中有效解决可分解的三角形问题（ProjectEuler）？

Question

我正在解决ProjectEuler上的问题，并且卡在了12th problem上，下面的代码花费的时间太长，甚至没有在五分钟内完成，并且我的CPU变热了。

本质上说，我在做的是通过添加连续的自然数来生成三角形的序列，例如：

• 1-> 1（即1）
• 2-> 3（即1 + 2）
• 3-> 6（即1 + 2 + 3）

依此类推，然后找到第一个三角数，该数具有500个因数（即501个因数）。

fun main() {
    val numbers = generateTriangularNumbers()
    val result = numbers.first {
        val count = factorOf(it).count()
        //        println(count) // just to see the count
        count > 500
    }
    println(result)
}

// Finds factor of input [x]
private fun factorOf(x: Long): Sequence<Long> = sequence {
    var current = 1L
    while (current <= x) {
        if (x % current == 0L) yield(current++) else current++
    }
}

// generates triangular numbers, like 1, 3, 6, 10. By adding numbers like 1+2+3+...n.
private fun generateTriangularNumbers(from: Long = 1): Sequence<Long> = sequence {
    val mapper: (Long) -> Long = { (1..it).sum() }
    var current = from
    while (true) yield(mapper(current++))
}

[计数（三角数的因子数）几乎不超过200，是否有办法在一分钟内有效解决此问题？

Answer 1

欧拉计划是关于数学的。编程排在第二位。您需要做一些作业。

• 证明三角数为n*(n+1)/2的形式。不重要。
• 证明n和n+1是互质的。不重要。
• [证明或至少说服自己，d(n)是multiplicative。

合并这些知识以提出一种有效的算法。您不需要实际计算三角数，而需要将数字分解小得多。记忆也可以避免很多分解。