Q

如何找到兩個數字的最小公倍數（LCM）

2011-11-01 110 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

相關問題