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

Question

我正在努力解决Project Euler中的问题#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但不到十亿,所以如果有效地完成,可以在几分钟内计算出来