两个数字的LCM

我的LCM计划结果出错了。

如果找到数字的gcd，然后用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; } 

任何帮助非常感谢。

Answer 1

你的gcd函数总是返回0 。 更改

 return y; 

至

 return x; 

理解Euclid的算法：

 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 。

此外，在计算lcm时，您将首先乘以可能导致溢出的数字。 相反，你可以这样做：

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

但如果lcm不能适合int你必须long long

Answer 2

问题1） int gcd = gcd(x,y);

gcd已被定义为一个函数。 您无法定义具有相同名称的变量。

问题2）改变return y以return x gcd() return x ，否则每次都会返回0。

问题3）如果x和y很大， x * y可能会溢出。

Answer 3

您应该在gcd函数中返回x而不是y。

此外，您确定产品x * y将始终适合int吗？ 这也可能是一个好主意。

Answer 4

 #include  using namespace std; long long gcd(long long int a, long long int b){ if(b==0) return a; return gcd(b,a%b); } long long lcm(long long a,long long b){ if(a>b) return (a/gcd(a,b))*b; else return (b/gcd(a,b))*a; } int main(){ long long int a ,b ; cin>>a>>b; cout< 

Answer 5

该C程序是寻找LCM的不同方法

  #include int main() { int a,b,lcm=1,i=2; printf("Enter two numbers to find LCM\n" ); scanf("%d %d",&a ,&b); while(i <= a*b) { if(a%i==0 & b%i==0) { lcm=lcm*i; a=a/i; b=b/i; i=i-1; } if( a%i==0 & b%i!=0) { lcm=lcm*i; a=a/i; i=i-1; } if( b%i==0 & a%i!=0) { lcm=lcm*i; b=b/i; i=i-1; } i++; } printf("The LCM of numbers is %d\n", lcm); }