项目欧拉5
2520是可以除以1到10中的每个数字而没有任何余数的最小数字。
可以被1到20的所有数字整除的最小正数是多少?
我的解决方案
#include int gcd(int m, int n); int lcm(int a, int b); int main() { int x=1, i; for(i=1; in) m=mn; else n=nm; } return m; } int lcm(int a, int b) { return ((a*b)/gcd(a, b)); }
请告诉我哪里错了? 它在运行时仅显示空白屏幕。
如果您应该只从本练习中学到一个课程,那就这样做:您进行乘法和除法的顺序很重要 。
即使它在数学中无关紧要,但它通常在你的程序中很重要。 例如,在数学中, (a*b)/gcd(a, b)
和a/gcd(a, b)*b
之间没有区别; 在你的程序中,它会在传递和失败之间产生差异。
(PS当然你也需要修复逻辑中的错误:你不应该将x
乘以lcm)。
编辑
要了解订单在这里产生差异的原因,请考虑计算lcm
为232792560
和20
。 232792560
可以被20
整除,所以它是lcm
。 但是,当你计算232792560*20
,会出现溢出; 然后你除以20
,但你没有得到232792560
。
由于除数是gcd(a,b)
,你可以将它除以a
之前乘以b
而不用整数除法截断结果。 经验丰富的程序员在不假思索地使用这个小技巧可以节省数小时的调试时间。
Project Euler上的大多数问题都可以通过三种方式解决:
- 用蛮力
- 使用一种解决更普遍问题的算法(就像你一样)
- 智能解决方案最多需要铅笔和纸张
如果您对一个不错的解决方案感兴趣而不是修复代码,请尝试专注于最后一种方法:
诀窍是找到最小的多重素数,使得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接受。
printf()
会向您显示您的代码正在进入无限循环。 我在while
循环中的gcd()
中添加了printf()
。
n=nm; printf("m=%dn=%d\n", m, n); } return m;
while(m!=n)
对于n=14
while(m!=n)
永远不会成立。 最后m
和n
溢出,因为x
变为更高的数字, int
类型无法容纳!
错误是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)); }
n-1应为n; 和x = lcm(…)不是x * = lcm(…)。 但是我并没有完全看到(远离终端)你的循环被卡住的地方。
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 <== Euler 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