欧拉项目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

回答

相关问题