2

我正在尝试解决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
4

3 回答 3

11

仅通过计算每个可能的解决方案无法找到该问题的解决方案。解决方案是如此之大，以至于需要数天（可能是数年）来计算。

有一个更聪明的解决方案是使用素数来记下这些数字。

给出的示例（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 亿，因此如果有效完成，可以在几分钟内计算出来

于 2010-06-04T12:36:32.420 回答
0

该问题本质上是要求您找到前 20 个数字的 LCM...

lcm = 1
for i = 2 to 20
   lcm = (i * lcm) / gcd(lcm,i)
于 2010-06-09T09:22:36.970 回答
0

一个更简单的解决方案是使用您的算法，但增加 2520 而不是 1，这是我的 C++ 解决方案。

#include <iostream>
using namespace std;

int main()
{
    int check = 2520;
    int i = 11;
    while (i != 20)
    {
        i ++;
        if (check % i != 0)
        {
            check +=2520;
            i = 1;
        }
    }
    cout << check << endl;
    return 0;
}

正如您在上面看到的，我也从数字 2520 开始，并将 i 设置为等于 11。我们可以进行这些优化，因为我们已经在问题中获得了必要的信息。

于 2010-09-29T12:42:40.850 回答