计算 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.

我对逻辑的看法

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

我发现的问题

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

对第 5 号（粗体）的 gcd 逻辑和评论有什么建议吗？

谢谢

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)

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

Calculating GCD - how to check every element in list

python

algorithm

list

greatest-common-divisor