计算两个整数的最小公倍数的最有效方法是什么？

Question

计算两个整数的最小公倍数的最有效方法是什么？

我想出了这个,但它确实留下了一些不足之处.

int n=7, m=4, n1=n, m1=m;

while( m1 != n1 ){
    if( m1 > n1 )
        n1 += n;
    else 
        m1 += m;
}

System.out.println( "lcm is " + m1 );

Answer 1

最小公倍数(lcm)a和b它们的乘积除以它们的最大公约数(gcd)(即lcm(a, b) = ab/gcd(a,b)).

那么,问题就变成了,如何找到gcd？该欧几里德算法是最大公因数一般是如何计算的.经典算法的直接实现是有效的,但有些变体利用二进制算法做得更好.参见Knuth的" 计算机程序设计的艺术 " 第2卷,"研究数学算法"§4.5.2.

Answer 2

记住,最小公倍数是最小整数,它是两个或多个数字中每一个的倍数.

如果您试图找出三个整数的LCM,请按照下列步骤操作:

  **Find the LCM of 19, 21, and 42.**

为每个数字写出素数因子分解.19是素数.你不需要考虑因素19.

21 = 3 × 7
42 = 2 × 3 × 7
19

重复每个素数因子在上述任何主要因子分解中出现的最大次数.

2×3×7×19 = 798

21,42和19的最小公倍数是798.

Answer 3

下面的 C++ 最佳解决方案不会溢出

#include <iostream>
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<<lcm(a,b)<<endl;        
    return 0;
}