Q

如何找到两个数字的最小公倍数（LCM）

2011-11-01 108 views -1 likes

-1

我已经使用Euclid的方法找到L.C.M两个数字。如何找到两个数字的最小公倍数（LCM）

l.c.m=a*b/(gcd(a,b))

如何在不使用此算法的情况下做到这一点？我有一个想法，首先获取这两个数字的所有因素，并将它们存储在数组中。然后从数组1中取1个元素并在数组2中搜索它，如果它出现在那里然后从那里移除它并将结果乘以那个数。

可以吗？

2011-11-01 Sharpzain120

+0

听起来像是家庭作业 – pnezis

+0

Java还是C++？根据不同的语言，解决方案可能会有所不同。 –

+0

最好是使用'（a/gcd（a，b））* b'来避免整数溢出。使用因式分解来计算'lcm'比使用'gcd'效率低得多。 – starblue

A

回答

1

差不多。什么是4和8的LCM？显然8（2 ），但在你的方法中，你会发现2.你需要跟踪不仅仅是所有因素，而且还要跟踪它们出现的频率。

2011-11-01 15:18:45 MSalters

+1

实际上8和4不是4和8的LCM吗？ GCD（8,4）产生4，所以（8 * 4）/ 4 = 8，所以问题中的公式会产生正确答案？ LCM必须至少与两个输入值中较大的一样大（假设所有正数）。 –

+0

呃，是的，是固定的。 GCD和LCM方法密切相关。如果在素数因子中考虑这两个项，取各自的最小值并乘以它们，得到GCD（这里：min（2,3）= 2，2x2 = 4）。采取呼吸最大值（这里：max（2,3）= 3,2x2x2 = 8），并获得LCM。 – MSalters

1

我相信你建议的算法是a method using a table，请检查它是否适合你。

2011-11-01 15:03:44

+1

他的方法实际上是[素因分解]（https://secure.wikimedia.org/wikipedia/en/wiki/Least_common_multiple#Finding_least_common_multiples_by_prime_factorization）。但是，它是有效的。 – MSalters

相关问题