Python 程序：求最小公倍数 (LCM)

两个数的最小公倍数 (L.C.M.) 是能被这两个给定的数整除的最小正整数。

例如，12 和 14 的最小公倍数是 84。

计算最小公倍数的程序

# Python Program to find the L.C.M. of two input number

def compute_lcm(x, y):

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

num1 = 54
num2 = 24

print("The L.C.M. is", compute_lcm(num1, num2))

输出

The L.C.M. is 216

注意：要测试此程序，请更改 num1 和 num2 的值。

此程序将两个数分别存储在 num1 和 num2 中。这些数被传递给 compute_lcm() 函数。该函数返回两个数的最小公倍数。

在函数中，我们首先确定两个数中较大的一个，因为最小公倍数只能大于或等于较大的数。然后，我们使用一个无限的 while 循环从这个数开始不断增加。

在每次迭代中，我们检查我们的数是否能被两个给定的数整除。如果可以，我们就将这个数存储为最小公倍数并跳出循环。否则，该数加 1，循环继续。

上述程序的运行速度较慢。我们可以利用“两个数的乘积等于它们的最小公倍数与最大公约数的乘积”这一事实来提高效率。

Number1 * Number2 = L.C.M. * G.C.D.

以下是一个实现此方法的 Python 程序。

使用最大公约数 (GCD) 计算最小公倍数 (LCM) 的程序

# Python program to find the L.C.M. of two input number

# This function computes GCD 
def compute_gcd(x, y):

   while(y):
       x, y = y, x % y
   return x

# This function computes LCM
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

num1 = 54
num2 = 24 

print("The L.C.M. is", compute_lcm(num1, num2))

此程序的输出与之前相同。我们有两个函数：compute_gcd() 和 compute_lcm()。我们需要数的最大公约数 (G.C.D.) 来计算它们的最小公倍数 (L.C.M.)。

因此，compute_lcm() 调用 compute_gcd() 函数来完成此任务。可以使用欧几里得算法高效地计算两个数的最大公约数。

另请阅读

• 在 Python 中计算最大公约数