歐拉項目5

2520是可以被從1到10的每個數字除以沒有任何餘數的最小數字。歐拉項目5

可以被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)); 
}

請告訴我在哪裏錯了？它只顯示運行中的空白屏幕。

來源

2011-12-27 Amit Tiwari

當加入額外的打印語句，你學到了什麼？ – 2011-12-27 13:48:45

我在哪裏添加額外的打印語句？ – 2011-12-27 14:23:09

他在說你應該縮小你正陷入困境的地方。 – gnometorule 2011-12-27 14:24:27

如果您在本練習中應該只學到一門課，請將其設置爲：您的乘法和分割的順序很重要。

即使數學不重要，它在您的程序中也很重要。例如，在數學中，(a*b)/gcd(a, b)和a/gcd(a, b)*b之間沒有區別;在你的程序中，它會在通過和失敗之間做出區別。（當然你也需要修正你的邏輯中的錯誤：你不應該把x乘以1釐米）。

編輯

要理解爲什麼爲了使得這裏的區別，考慮計算的232792560和20lcm。 232792560可由20整除，所以它是lcm。但是，當您計算232792560*20時，會發生溢出;那麼你除以20，但你沒有得到232792560回來。

由於除數爲gcd(a,b)，可以將它除以a，然後再乘以b，而不用整數除法截斷結果。有經驗的程序員不經過思考就可以使用這個小技巧可以節省數小時的調試時間

來源

2011-12-27 14:16:46 dasblinkenlight

雅..我明白這一點，但括號是正確的放在我的代碼我想。 – 2011-12-27 14:27:32

@AmitTiwari不，他們沒有放在正確的位置。嘗試一下！ – dasblinkenlight 2011-12-27 14:30:14

@Amit：如果（a * b）溢出'int'數據類型，則不會。 – 2011-12-27 14:33:40

A 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類型容納！

來源

2011-12-27 14:01:40

這有什麼解決辦法？ – 2011-12-27 14:25:00

n-1應該是n;和x = 1cm（...）而不是x * = 1cm（...）。但我不太清楚（遠離終端）你的環路卡在哪裏。

來源

2011-12-27 14:13:56 gnometorule

好的..我修正了上面的錯誤。答案是18044195.但是，這不是正確的答案。 – 2011-12-27 14:26:31

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

來源

2011-12-27 14:23:25 joshu

這也給出18044195. – 2011-12-27 14:40:23

和18044195不是正確的答案。而且你不能在for循環中聲明我很長。 – 2011-12-27 14:42:57

'printf（）'中提到''long'的格式說明符不正確！ ..對於正確的格式說明符檢查'printf（）'手冊頁或[這裏]（http://en.wikipedia.org/wiki/Printf_format_string#Format_placeholders） – 2011-12-27 15:00:16

上項目歐拉大多數問題都可以通過三種方式解決：

用蠻力
與算法解決了一個更普遍的問題（像你一樣）
帶智能解決方案，最多需要鉛筆和紙張

如果你有興趣在一個不錯的解決方案，而不是解決你的代碼，嘗試集中在最後一種方法：

關鍵是要找到素數的最小的多集，使得1和20之間的任意數字被表示爲這些素數中的一些的乘積。

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

通過「或門」爲1到10之間的數字的主要因素，我們得到1*2*2*2*3*3*5*7，這恰好是2520，正如預期。

現在，如果我們從1到20，我們得到1*2*2*2*2*3*3*5*7*11*13*17*19，這確實被Project Euler接受。

來源

2011-12-27 14:33:44 Philip

好的..我猜，我試着說我應該找到20以下的素數，並使用素因子分解，我應該計算lcm，這應該是答案..我是對嗎？ – 2011-12-27 14:52:40

我編輯了我的帖子，使其更清楚我的意思。忘掉lcm，訣竅就是利用素數分解。 – Philip 2011-12-27 14:56:39

什麼是「ORing」？ – 2011-12-27 15:11:49

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：232792560 <歐拉PROG 5 ==答案（1至20而不剩餘
21：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

來源

2015-01-03 16:36:40

回答

相關問題