什麼是計算兩個整數的最小公倍數的最有效方法？

Question

什麼是計算兩個整數的最小公倍數的最有效方法？

我剛想出這個，但它肯定會留下一些不盡人意的地方。

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

Answer 1

的a和b最小公倍數（LCM）是他們的產品通過自己的最大公約數（GCD）（即lcm(a, b) = ab/gcd(a,b)）劃分。

那麼，問題就變成了，如何找到gcd？ Euclidean algorithm一般是如何計算gcd的。經典算法的直接實現是高效的，但是有一些變體可以利用二進制算法做得更好一些。見Knuth的「The Art of Computer Programming」Volume 2, "Seminumerical Algorithms" § 4.5.2。

Answer 2

取兩個數中較大者的連續倍數，直到結果爲較小值的倍數。

這可能工作..

public int LCM(int x, int y) 
    { 
     int larger = x>y? x: y, 
      smaller = x>y? y: x, 
      candidate = larger ; 
     while (candidate % smaller != 0) candidate += larger ; 
     return candidate; 
    } 

Answer 3

我認爲「reduction by the greatest common divider」的做法應該更快。首先計算GCD（例如使用Euclid's algorithm），然後將這兩個數的乘積除以GCD。

Answer 4

請記住 最小公倍數是整數的最小值，它是兩個或更多數字中每一個的倍數。

如果你想找出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

Answer 5

首先，你必須找到最大公約數

for(int = 1; i <= a && i <= b; i++) { 

    if (i % a == 0 && i % b == 0) 
    { 
     gcd = i; 
    } 

} 

之後，使用GCD可以輕鬆地找到最小公倍數這樣

lcm = a/gcd * b; 

Answer 6

，我不知道是否進行了優化或沒有，但可能是最簡單一個：

public void lcm(int a, int b) 
{ 
    if (a > b) 
    { 
     min = b; 
     max = a; 
    } 
    else 
    { 
     min = a; 
     max = b; 
    } 
    for (i = 1; i < max; i++) 
    { 
     if ((min*i)%max == 0) 
     { 
      res = min*i; 
      break; 
     } 
    } 
    Console.Write("{0}", res); 
} 

Answer 7

在C++中最好的解決辦法如下而不溢出

#include <iostream> 
using namespace std; 
long long gcd(long long int a, long long int b){   
    if(b==0) 
     return a; 
    return gcd(b,a%b); 
} 

long long lcm(long long a,long long b){  
    if(a>b) 
     return (a/gcd(a,b))*b; 
    else 
     return (b/gcd(a,b))*a;  
} 

int main() 
{ 
    long long int a ,b ; 
    cin>>a>>b; 
    cout<<lcm(a,b)<<endl;   
    return 0; 
} 

Answer 8

C++模板。編譯時間

#include <iostream> 

const int lhs = 8, rhs = 12; 

template<int n, int mod_lhs=n % lhs, int mod_rhs=n % rhs> struct calc { 
    calc() { } 
}; 

template<int n> struct calc<n, 0, 0> { 
    calc() { std::cout << n << std::endl; } 
}; 

template<int n, int mod_rhs> struct calc<n, 0, mod_rhs> { 
    calc() { } 
}; 

template<int n, int mod_lhs> struct calc <n, mod_lhs, 0> { 
    calc() { } 
}; 

template<int n> struct lcm { 
    lcm() { 
    lcm<n-1>(); 
    calc<n>(); 
    } 
}; 

template<> struct lcm<0> { 
    lcm() {} 
}; 

int main() { 
    lcm<lhs * rhs>(); 
} 

Answer 9

2個數字的乘積等於LCM * GCD或HCF。因此找到LCM的最佳方式是找到GCD並將產品與GDC分開。