Project Euler 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));
}请告诉我哪里错了？运行时只显示空白屏幕。
回答 7
Stack Overflow用户
发布于 2011-12-27 22:16:47
如果你只能从这个练习中学到一课，那就让它变成这样:你做乘法和除法的顺序很重要()。
即使它在数学中无关紧要，它在你的程序中通常也很重要。例如，在数学中，(a*b)/gcd(a, b)和a/gcd(a, b)*b之间没有区别；在您的程序中，它将决定通过和失败之间的区别。
(附言:当然，您也需要修复逻辑中的错误:您不应该将x乘以lcm)。
编辑
要理解为什么顺序会在这里有所不同，请考虑计算232792560和20的lcm。232792560可以被20整除，所以它是lcm。但是，当您计算232792560*20时，会得到一个溢出；然后除以20，但不会得到232792560。
由于除数是gcd(a,b)，您可以在乘以a之前将其除以b，而无需通过整数除法截断结果。这是经验丰富的程序员不假思索地使用的小技巧，可以节省您的调试时间。
Stack Overflow用户
发布于 2011-12-27 22:33:45
Project Euler上的大多数问题可以通过三种方式解决：
使用brute-force
- with的
- 算法可以解决更一般的问题(就像您一样)
- 具有智能的解决方案，最多只需要纸和笔
如果你对一个很好的解决方案感兴趣，而不是修复你的代码，试着专注于最后一种方法：
技巧是找到质数的最小多集，使得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通过"ORing“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接受。
Stack Overflow用户
发布于 2011-12-27 22:01:40
一个printf()会告诉你你的代码进入了一个无限循环。我已经在while循环的gcd()中添加了一个printf()。
n=n-m;
printf("m=%d n=%d\n", m, n);
}
return m;对于n=14来说，while(m!=n)从来都不是真的。最后，m和n溢出，因为x达到了一个更高的数字，而int类型无法容纳这个数字！
https://stackoverflow.com/questions/8645301
复制相似问题
腾讯云开发者
