プロジェクトオイラー5

Question

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)); 
} 

私が間違っているところ教えてください？実行中は空白の画面しか表示されません。

Answer 1

このレッスンで学んだレッスンは1つだけにする必要があります。乗算と除算の順序は、です。

数学で重要ではないにしても、あなたのプログラムでは重要なことがよくあります。たとえば、数学では(a*b)/gcd(a, b)とa/gcd(a, b)*bの間に違いはありません。あなたのプログラムでは、成功と失敗の違いがあります。

（もちろん、ロジックにもバグを修正する必要があります：xにlcmを掛けてはいけません）。順序はここに違いがなぜ

EDIT

は232792560と20のlcmを計算検討し、理解するために。 232792560は20で割り切れるので、lcmです。しかし、232792560*20を計算すると、オーバーフローが発生します。次に20で割りますが、232792560は戻ってきません。

除数はgcd(a,b)なので、結果を整数除算で切り捨てずにbを掛ける前にaから除算することができます。プログラマーが思考せずに使用しているこの小さなトリックは、何時間ものデバッグを節約できます。

Answer 2

printf()は、コードが無限ループに入っていることを示しています。ループwhileのgcd()にprintf()を追加しました。

n=n-m; 
    printf("m=%d n=%d\n", m, n); 
} 
return m; 

while(m!=n)n=14のために真になることはありません。最後にmとnがオーバーフローします。xは、intタイプでは対応できない高い数値になります。

Answer 3

n-1はnにする必要があります。 x = 1cm（...）ではなく、x * = 1cm（...）である。しかし、私はあなたのループが詰まっているところを（ターミナルから離れて）かなり見ない。

Answer 4

バグがx*=lcm(x, i+1);であり、ここで完全なソリューションである、プロジェクトオイラーの

long gcd(long m, long n); 
long lcm(long a, long b); 

int main() 
{ 
    long x=1; 
    for(int i=2; i<=20; i++) 
    { 
     x=lcm(x,i); 
    } 
    cout << "The answer is: " << x << endl; 
    return 0; 
} 

long gcd(long a, long b) 
{ 
     return (b==0)?a:gcd(b,a%b); 
} 

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

Answer 5

ほとんどの問題は、以下の3つの方法で解決することができます。

• ブルートフォース
• とアルゴリズムでより一般的な問題を解決する（あなたのように）
• 鉛筆と紙を多く必要とするスマートなソリューションで

あなたは素敵な解決策ではなく、あなたのコードを固定に興味があるなら、最後のアプローチに集中してみてください：

は

トリックは、このようなことを素数の最小のマルチセットを見つけることである1と20缶の間の任意の数これらの素数のいくつかの積として表すことができます。 「和」1から10までの数字のための主な要因によって

1 = 1  11 = 11 
2 = 2  12 = 2*2*3 
3 = 3  13 = 13 
4 = 2*2 14 = 2*7 
5 = 5  15 = 3*5 
6 = 2*3 16 = 2*2*2*2 
7 = 7  17 = 17 
8 = 2*2*2 18 = 2*3*3 
9 = 3*3 19 = 19 
10 = 2*5 20 = 2*2*5 

、私たちは期待と同じように、2520年であることを起こるおり、1*2*2*2*3*3*5*7を取得します。

1から20になると、実際にProject Eulerに受け入れられる1*2*2*2*2*3*3*5*7*11*13*17*19が得られます。

Answer 6

20の答えは232792560です。

これらは全て答えが長い整数に適合するの全ての数のための答えである：

1：1
2：2
3：6
4：12
5：60
6：60
7：420
8：840
9：2520
10：2520 <オイラーP5で===例残りせずに1〜10による除算のための質問
11：27720
12：27720
13：360360
14：360360
15：360360
16：720720
17：12252240
18：12252240
19：232792560
20：オイラーのProg 5ため232792560 < ==回答残り
21無し20（1：232792560
22：232792560
23：5354228880
24：5354228880
25：26771144400
26：26771144400
27：80313433200
28：80313433200
29：2329089562800
30：2329089562800
31：72201776446800
32：144403552893600
33：144403552893600
34：144403552893600
35：144403552893600
36：144403552893600
37：5342931457063200
38：5342931457063200
39：5342931457063200
40：5342931457063200
41：219060189739591200
42：219060189739591200