ruby - 为什么我的代码不会停止运行？

Question

我正在尝试解决 Problem #5在欧拉计划中。该代码适用于该示例，当我检查从 1 到 10 的数字时，结果是 2520，这是正确的。但是当我检查从 1 到 20 的数字时，代码并没有停止运行。

这里是:

num = 0

while true

    num += 1
    check = true

    for i in 1..20

        break unless check

        check = num%i==0

    end

    break if check

end

File.open("__RESULT__.txt", "w+").write num

Answer 1

仅通过计算所有可能的解决方案是无法找到该问题的解决方案的。解决方案太大，需要几天(也许几年)才能计算出来。

有一个更聪明的解决方案，使用素数来写下数字。

给出的示例(2520 是可被数字 1 到 10 整除的最小数字)可以这样写:

1 = 1 (can be skipped)  = 2^0 * 3^0 * 5^0 * 7^0
2 = 2 (prime)           = 2^1 * 3^0 * 5^0 * 7^0
3 = 3 (prime)           = 2^0 * 3^1 * 5^0 * 7^0
4 = 2^2                 = 2^2 * 3^0 * 5^0 * 7^0
5 = 5 (prime)           = 2^0 * 3^0 * 5^1 * 7^0
6 = 2 * 3               = 2^1 * 3^1 * 5^0 * 7^0
7 = 7 (prime)           = 2^0 * 3^0 * 5^0 * 7^1
8 = 2^3                 = 2^3 * 3^0 * 5^0 * 7^0
9 = 3^2                 = 2^0 * 3^2 * 5^0 * 7^0
10= 2 * 5               = 2^1 * 3^0 * 5^1 * 7^0

现在可以除以这些的最小数，可以通过使用每个素数的最大幂来计算:

2^3 * 3^2 * 5^1 * 7^1 = 2520

可以对数字 1 到 20 执行相同的操作(甚至是手动操作)

最后提示:答案大于 100.000.000 但小于 10 亿，因此如果高效地计算，可以在几分钟内计算