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 = 1
for i = 2 to 20
   lcm = (i * lcm) / gcd(lcm,i)
于 2010-06-09T09:22:36.970 に答える
0

はるかに簡単な解決策は、アルゴリズムを使用することですが、1 ではなく 2520 ずつインクリメントします。これが私の 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 に答える