如何在 Kotlin 中有效地解决可分三角问题 (ProjectEuler)？

Question

我在 ProjectEuler, And I am stuck on the 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。

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

如何在 Kotlin 中有效地解决可分三角问题 (ProjectEuler)？

How to solve divisible triangular problem (ProjectEuler) efficiently in Kotlin?

algorithm

numbers

factors

kotlin