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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (79)

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

我刚刚提出这个问题,但它肯定会留下一些不足之处。

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 );
提问于
用户回答回答于

其最小公倍数(lcm)ab它们的产品除以它们的最大公约数(gcd)(ie lcm(a, b) = ab/gcd(a,b))。

那么,问题就变成了,如何找到gcd?该Euclidean算法是最大公因数一般是如何计算的。经典算法的直接实现是高效的,但是有一些变体可以利用二进制算法做得更好一些。见“ 计算机程序设计艺术第2卷,“研究数学算法”第4.5.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。

扫码关注云+社区

领取腾讯云代金券