两个数字的LCM

本文介绍了两个数字的LCM的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我的LCM程序得到错误的结果.

I am getting wrong result for my LCM program.

我首先找到数字的gcd，然后将其除以gcd.

Ifirst find gcd of the numbers and then divide the product with gcd.

int gcd(int x, int y) { while(y != 0) { int save = y; y = x % y; x = save; } return y; } int lcm(int x, int y) { int prod = x * y; int Gcd = gcd(x,y); int lcm = prod / Gcd; return lcm; }

非常感谢您的帮助.

推荐答案

您的gcd函数将始终返回0.更改

Your gcd function will always return 0. Change

return y;

到

return x;

了解Euclid算法:

Understand the Euclid's algorithm:

RULE 1: gcd(x,0) = x RULE 2: gcd(x,y) = gcd(y,x % y)

考虑x = 12和y = 18

gcd (12, 18) = gcd (18, 12) Using rule 2 = gcd (12,6) Using rule 2 = gcd (6, 0) Using rule 1 = 6

如您所见，当y变为零时，x将是gcd，因此您需要返回x而不是y.

As you can see when y becomes zero x will be the gcd so you need to return x and not y.

此外，在计算lcm时，您首先将数字相乘会导致溢出.相反，您可以执行以下操作:

Also while calculating lcm you are multiplying the numbers first which can cause overflow. Instead you can do:

lcm = x * (y / gcd(x,y))

，但是如果lcm无法容纳在int中，则必须将其设置为long long

but if lcm cannot fit in an int you'll have to make it long long