[解決済み] プロジェクト・オイラー5

質問

2520は、1から10までの各数字で余すことなく割り切れる最小の数である。

1から20までのすべての数で均等に割り切れる最小の正の数は何でしょう？

私の解答です。

#include<stdio.h>
int gcd(int m, int n);
int lcm(int a, int b);
int main()
{
    int x=1, i;
    for(i=1; i<20; i++)
    {
        x=lcm(x, i+1);
    }
    printf("The answer is:\t%d", x);
    return 0;
}

int gcd(int m, int n)
{
    while(m!=n)
    {
        if(m>n)
        m=m-n;
        else
        n=n-m;
    }
    return m;
}

int lcm(int a, int b)
{
    return ((a*b)/gcd(a, b));
}

どこが間違っているのか、教えてください。実行すると空白の画面しか表示されません。

どうすればいいですか？

この演習から学ぶべき教訓が1つだけあるとすれば、それはこれです。 掛け算と割り算の順番は重要です。 .

数学では問題にならなくても、プログラムでは問題になることがよくあります。例えば、数学の世界では (a*b)/gcd(a, b) と a/gcd(a, b)*b あなたのプログラムでは、それが合格と不合格の違いになるのです。

(追記) もちろん、ロジックのバグも修正する必要があります。 x をlcmで割ったもの)。

EDIT

なぜここで順序が違いを生むのかを理解するために、計算を考えてみましょう。 lcm の 232792560 と 20 . 232792560 で割り切れる。 20 であるので、それは lcm . ただし、計算するときは 232792560*20 で割ると、オーバーフローが発生します。 20 が得られません。 232792560 を返します。

であるため、除数は gcd(a,b) から割り出すことができます。 a を掛ける前に b のように、整数の除算で結果を切り捨てることなく、計算することができます。経験豊富なプログラマーが何気なく使っているこの小さなトリックが、デバッグの時間を短縮してくれるのです。