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

I'm trying to solve Problem #5 in Project Euler. The code works for the example, when I check the numbers from 1 to 10 I get 2520 as a result, which is right. But when I check for the numbers from 1 to 20, the code doesn't stop running.

我正在解决欧拉项目中的第5个问题。这个代码适用于这个示例，当我从1到10检查数字时，结果是2520，这是正确的。但是当我检查从1到20的数字时，代码并没有停止运行。

Here it is:

这里是:

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

3 个解决方案

#1

The solution for that problem can not be found by just calculating every possible solution. The solution is so big, that it will take days (maybe years) to calculate.

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

There is a smarter solution using prime numbers to write down the numbers.

有一种更聪明的方法，用素数写下这些数字。

The example that is given (2520 is the smallest number that is divisable by the numbers 1 through 10) can be written down like this:

举个例子(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

Now the smallest number that can be divided by these, can be calculated by using the maximum power that is used on each prime:

现在最小的数可以除以这些，可以用每个素数的最大功率来计算:

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

The same can be performed (even by hand) on the numbers 1 through 20

在数字1到20之间也可以执行相同的操作(即使是手动的)。

Last hint: the answer is larger than 100.000.000 but less that a billion, so it can be calculated in minutes if done efficiently

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

#2

The Question essentially asks you to find the LCM of the first 20 numbers...

问题本质上是问你找到前20个数字的LCM……

lcm = 1
for i = 2 to 20
   lcm = (i * lcm) / gcd(lcm,i)

#3

A far simpler solution would be to use your algorithm but increment by 2520 rather than 1, here is my C++ solution.

一个简单得多的解决方案是使用你的算法但是增加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;
}

As you can see above, I also start at the number 2520, and set i to equal 11. We can make these optimizations, as we have been given the necessary information in the question.

如你所见，我也从2520开始，将I设为11。我们可以进行这些优化，因为我们已经在这个问题中获得了必要的信息。

#1