计算两个整数的最小公倍数的最有效方法是什么?
我刚刚想出了这个,但它确实留下了一些令人期待的东西。
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 );
发布于 2010-07-01 09:07:01
a
和b
的最小公倍数是它们的乘积除以它们的最大公约数(即lcm(a, b) = ab/gcd(a,b)
)。
因此,问题变成了,如何找到gcd?Euclidean algorithm通常是计算gcd的方式。经典算法的直接实现是有效的,但是有一些变体利用二进制算法来做得更好一些。请参阅Knuth的"The Art of Computer Programming“Volume 2, "Seminumerical Algorithms" § 4.5.2。
发布于 2010-07-01 09:09:47
我认为"reduction by the greatest common divider“的方法应该更快。首先计算GCD (例如使用Euclid's algorithm),然后将两个数字的乘积除以GCD。
发布于 2015-11-25 02:55:02
首先,你必须找到最大的公约数
for(int i=1; i<=a && i<=b; i++) {
if (i % a == 0 && i % b == 0)
{
gcd = i;
}
}
在此之后,使用GCD,您可以很容易地找到最小公倍数,如下所示
lcm = a / gcd * b;
https://stackoverflow.com/questions/3154454
复制相似问题