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

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？ 欧几里得算法通常是计算 gcd 的方法。经典算法的直接实现是高效的，但是有一些变体利用二进制算术来做得更好一些。请参阅 Knuth 的“计算机编程艺术" 第 2 卷，“半数值算法”§ 4.5.2。

Answer 2

记住
最小公倍数是两个或多个数字中每个数字的倍数的最小整数。

如果您试图计算三个整数的最小公倍数，请按照下列步骤操作：

  **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 3

下面的 C++ 最佳解决方案不会溢出

#include <iostream>
#include <tuple>

long long gcd(long long a, long long b) {       
    while (b != 0)
        std::tie(a, b) = std::make_tuple(b, a % b);
    return a;
}

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 a, b;
    std::cin >> a >> b;
    std::cout << lcm(a, b) << std::endl;        
    return 0;
}

Answer 4

我认为“按最大公约数减少”的方法应该更快。首先计算 GCD（例如使用欧几里得算法），然后除两个数字的乘积由GCD。

Answer 5

我不知道它是否已优化，但可能是最简单的：

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 6

扩展 @John D. Cook 答案，该答案也标记为该问题的答案。 （ https://stackoverflow.com/a/3154503/13272795），我正在分享查找 n 个数字的 LCM 的算法，可能是 2 个数字或任意数字的 LCM。此代码的来源是此

 int gcd(int a, int b)
 {
     if (b == 0)
         return a;
     return gcd(b, a % b);
 }

  // Returns LCM of array elements
 ll findlcm(int arr[], int n)
 {
    // Initialize result
     ll ans = arr[0];

   // ans contains LCM of arr[0], ..arr[i]
   // after i'th iteration,
       for (int i = 1; i < n; i++)
           ans = arr[i] * ans/gcd(arr[i], ans);
       return ans;
 }

Answer 7

连续取两个数中较大者的倍数，直到结果是较小者的倍数。

这可能有用..

   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 8

这是在 python 中查找两个数字的 LCM 的高效方法。

def gcd(a, b):
    if min(a, b) == 0:
        return max(a, b)
    a_1 = max(a, b) % min(a, b)
    return gcd(a_1, min(a, b))

def lcm(a, b):
    return (a * b) // gcd(a, b)

Answer 9

使用欧几里得算法找到 gcd，然后计算 lcm 除以 gcd 和 b 的乘积，这对我有用。

int euclidgcd(int a, int b){
        if(b==0)
        return a;
        int a_rem = a % b;
        return euclidgcd(b, a_rem);
        }
    
long long lcm(int a, int b) {
        int gcd=euclidgcd(a, b);
        return (a/gcd*b);
        }

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

Answer 10

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 11

2 个数字的乘积等于 LCM * GCD 或 HCF。所以求 LCM 的最好方法就是求 GCD 并用 GCD 划分乘积。即，LCM(a,b) = (a*b)/GCD(a,b)。

Answer 12

首先，你必须找到最大公约数

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

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

}

之后，使用GCD你可以轻松找到最小公倍数，如下所示

lcm = a / gcd * b;

Answer 13

没有比使用内置函数更有效的方法了！

从 Python 3.8 开始，数学库中添加了 lcm() 函数。并且可以使用以下签名进行调用：

math.lcm(*integers)

返回指定整数参数的最小公倍数。如果所有参数均非零，则返回值是所有参数的倍数的最小正整数。如果任何参数为零，则返回值为 0。不带参数的 lcm() 返回 1。

Answer 14

因为我们知道数学属性，即“任意两个数字的 LCM 和 HCF 的乘积等于这两个数字的乘积”。

假设 X 和 Y 是两个整数，
然后
X * Y = HCF(X, Y) * LCM(X, Y)

现在我们可以通过知道 HCF 来找到 LCM，我们可以通过欧几里德算法找到 HCF。

  LCM(X, Y) = (X * Y) / HCF(X, Y)

希望这会很有效率。

import java.util.*;
public class Hello {
    public static int HCF(int X, int Y){
        if(X == 0)return Y;
        return HCF(Y%X, X);
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int X = scanner.nextInt(), Y = scanner.nextInt();
        System.out.print((X * Y) / HCF(X, Y));
    }
}

Answer 15

是的，计算 LCM 的方法有很多种，例如使用 GCD (HCF)。
您可以应用素数分解，例如（优化/朴素）Sieve Eratosthenes 或查找素数因子来计算 GCD，这比直接计算 LCM 快得多。那么如上所述，LCM(X, Y) = (X * Y) / GCD(X, Y)

Answer 16

我用谷歌搜索了同样的问题，并找到了这个 Stackoverflow 页面，
我想出了另一个使用 python 的简单解决方案

def find_lcm(numbers):
    h = max(numbers)

    lcm = h

    def check(l, numbers):
        remainders = [ l%n==0 for n in numbers]
        return all(remainders)

    while (check(lcm, numbers) == False):
        lcm = lcm + h
    
    return lcm

不过
数字 = [120,150,135,225]
它将返回5400

numbers = [120,150,135,225]

print(find_lcm(numbers)) # will print 5400

Answer 17

欧几里得 GCD 代码片段

int findGCD(int a, int b) {
        if(a < 0 || b < 0)
            return -1;

        if (a == 0)
            return b;
        else if (b == 0)
            return a;
        else 
            return findGCD(b, a % b);
    }