计算两个整数的最小公倍数的最有效方法是什么? [英] What is the most efficient way to calculate the least common multiple of two integers?

问题描述

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

What is the most efficient way to calculate the least common multiple of two integers?

我只是想出了这个，但是肯定有一些不足之处.

I just came up with this, but it definitely leaves something to be desired.

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 );

推荐答案

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

The least common multiple (lcm) of a and b is their product divided by their greatest common divisor (gcd) ( i.e. lcm(a, b) = ab/gcd(a,b)).

所以，问题就变成了如何找到gcd? 欧几里得算法通常是计算gcd的方法.经典算法的直接实现是有效的，但是有些变化可以利用二进制算法来做得更好.请参见 Knuth 的"第2卷，"Seminumicalical Algorithms"第4.5.2节.

So, the question becomes, how to find the gcd? The Euclidean algorithm is generally how the gcd is computed. The direct implementation of the classic algorithm is efficient, but there are variations that take advantage of binary arithmetic to do a little better. See Knuth's "The Art of Computer Programming" Volume 2, "Seminumerical Algorithms" § 4.5.2.

这篇关于计算两个整数的最小公倍数的最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！