求两个数的LCM

Question

问题是要找到两个数字的LCM。我试着用两种方法解决这个问题。首先，使用LCM公式：

LCM (a,b)= a*b/GCD(a,b).

第二，通过找出每个数的倍数，然后找到第一个公共倍数。以下是我所写的守则：

代码1:

#Using the LCM formula LCM = a*b / gcd(a,b)
def LCM(x , y):
    """ define a function LCM which takes two integer inputs and return their LCM using the formula LCM(a,b) = a*b / gcd(a,b) """
    if x==0 or y == 0:
        return "0"

    return (x * y)/GCD(x,y)

def GCD(a , b):
    """ define a function GCD which takes two integer inputs and return their common divisor""" 
    com_div =[1]
    i =2
    while i<= min(a,b):
        if a % i == 0 and  b % i ==0:
            com_div.append(i)
        i = i+1
    return com_div[-1]

print LCM(350,1)
print LCM(920,350) 

代码2:

#Finding the multiples of each number and then finding out the least common multiple
def LCM(x , y):
    """ define a function LCM which take two  integerinputs and return their LCM"""
    if x==0 or y == 0:
        return "0"
    multiple_set_1  = []
    multiple_set_2  = []
    for i in range(1,y+1):
        multiple_set_1.append(x*i)
    for j in range(1,x+1):
        multiple_set_2.append(y*j)
    for z in range (1,x*y+1):
        if z in multiple_set_1:
            if z in multiple_set_2:
                return z
                break

print LCM(350,450)

我想知道其中哪一种是更好的解决问题的方法，以及为什么会这样。还建议应包括哪些其他边境案件。

Answer 1

关于第1版：

GCD(a, b)的时间复杂度为\ O(min(a，b))\$，中间存储需要一个数组。您可以通过按反向顺序迭代可能的除数来消除数组，以便在找到公共除数时可以尽早返回。

关于第2版：

LCM(x , y)的时间复杂度为\ O(xy)\$，中间存储需要两个数组，因此这比版本1更糟糕。您可以通过只计算一个数字的倍数来改进这一点，然后测试另一个数字的倍数(按反向顺序)，直到找到一个公共倍数，然后提前返回。

共同问题：

• LCM应该总是返回一个数字，在某些情况下，您的代码返回字符串"0"。
• 这两个函数都采用整数参数(根据docstring )，但对负输入不产生合理的结果。
• 代码中空白的使用是不一致的。示例:如果x==0或y == 0: i =2
• 通过在PEP8 8编码方式上检查代码，可以检测到更多的C12违规行为(其中大多数与间距有关)。

一个更好的算法

“欧氏算法”是一种著名的计算最大公因子的方法，它优于您的两种方法。

它已经可以在Python标准库中获得：

>>> from fractions import gcd   # Python 2
>>> from math import gcd        # Python 3
>>> gcd(123, 234)
3

这应该作为实现LCM函数的基础。

看一看https://rosettacode.org/wiki/Greatest_常见_divisor#Python，例如，如果您想自己实现GCD (用于教育目的)

def gcd_iter(u, v):
    while v:
        u, v = v, u % v
    return abs(u)

这很短，很简单，不需要额外的空间，而且速度很快:时间复杂度大约是\$ =O(\log(max(a，b))\$ (参见例如欧几里德算法的时间复杂度是多少？)。