python - 计算 GCD - 如何检查列表中的每个元素

Question

• 多个数字输入

下面是我选择开始编写代码的方式

def main():

numbers = input()
if numbers == "0":
    exit()
else:
    number_list = [int(i) for i in numbers.split()]

def calculate_gcd(number_list):
    for i in range(1,smallest_number(number_list)+1):
        for n in range(0,len(number_list)):
            if number_list[n] % i == 0:
               check_list += number_list[n]

more code - but not important for the question im asking
my code was hardly complete and only worked for max 3 size lists, sadly.

我是如何看待逻辑的

1. 读取输入->按空格分割，放入列表
2. 排序列表
3. 创建一个变量(除数)，并将其设置为1
4. while divisor <= sortedlist[0](列表中最小的) <强>5。如果每个元素 % divisor == 0，则 gcd = divisor，则 divisor+=1
5. 循环直到不再为真

我发现的问题

1. 它需要愚蠢的努力，它实际上不会运行并给出运行时错误。
2. 我找不到检查No.5(粗体)的方法 我知道有 gcd 函数，但它只处理两个输入。 归结为同一个问题，我如何确保“所有”元素除以零？

有什么关于制定 gcd 逻辑和评论 No.5(粗体)的建议吗？

谢谢

Answer 1

与其解决更大的问题，不如解决更小的问题。你如何找到两个数字的gcd？好吧，有多种算法可以解决这个问题。让我们使用迭代的:

def gcd_iterative(a, b):
    while b:
        a, b = b, a % b
    return a

现在，要意识到的一件事是，如果你有多个数字，并且你想找到所有数字的 gcd，那么它很简单:

gcd(gcd(...(a, b), c), ...)

简单来说，如果你想找到三个数字(a、b、c)的 gcd，那么你将执行以下操作:

gcd = gcd_iterative(a, b) 
gcd = gcd_iterative(gcd, c)

所以，现在如果您有一个数字列表，lst，您可以执行以下操作:

>>> gcd = lst[0]
>>> for num in lst[1:]:
        gcd = gcd_iterative(gcd, num)
>>> print(gcd)