Python 具有多个数字的欧几里德算法（GCD）？

Euclidean algorithm (GCD) with multiple numbers?

提问by Tetramputechture

So I'm writing a program in Python to get the GCD of any amount of numbers.

所以我正在用 Python 编写一个程序来获取任意数量的数字的 GCD。

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]


    # i'm stuck here, this is wrong
    for i in range(len(numbers)-1):
        print GCD([numbers[i+1], numbers[i] % numbers[i+1]])


print GCD(30, 40, 36)

The function takes a list of numbers. This should print 2. However, I don't understand how to use the the algorithm recursively so it can handle multiple numbers. Can someone explain?

该函数需要一个数字列表。这应该打印 2。但是，我不明白如何递归地使用该算法，以便它可以处理多个数字。有人可以解释一下吗？

updated, still not working:

更新了，还是不行：

def GCD(numbers):

    if numbers[-1] == 0:
        return numbers[0]

    gcd = 0

    for i in range(len(numbers)):
        gcd = GCD([numbers[i+1], numbers[i] % numbers[i+1]])
        gcdtemp = GCD([gcd, numbers[i+2]])
        gcd = gcdtemp

    return gcd

---

---

Ok, solved it

好的，解决了

def GCD(a, b):

    if b == 0:
        return a
    else:
        return GCD(b, a % b)

and then use reduce, like

然后使用reduce，比如

reduce(GCD, (30, 40, 36))

采纳答案by alexkonradi

Since GCD is associative, GCD(a,b,c,d)is the same as GCD(GCD(GCD(a,b),c),d). In this case, Python's reducefunction would be a good candidate for reducing the cases for which len(numbers) > 2to a simple 2-number comparison. The code would look something like this:

由于 GCD 是关联的，GCD(a,b,c,d)因此与GCD(GCD(GCD(a,b),c),d). 在这种情况下，Python 的reduce函数将是一个很好的候选者，可以将案例len(numbers) > 2简化为简单的 2 数比较。代码看起来像这样：

if len(numbers) > 2:
    return reduce(lambda x,y: GCD([x,y]), numbers)

Reduce applies the given function to each element in the list, so that something like

Reduce 将给定的函数应用于列表中的每个元素，因此类似于

gcd = reduce(lambda x,y:GCD([x,y]),[a,b,c,d])

is the same as doing

和做一样

gcd = GCD(a,b)
gcd = GCD(gcd,c)
gcd = GCD(gcd,d)

Now the only thing left is to code for when len(numbers) <= 2. Passing only two arguments to GCDin reduceensures that your function recurses at most once (since len(numbers) > 2only in the original call), which has the additional benefit of never overflowing the stack.

现在唯一剩下的就是为 when 编码len(numbers) <= 2。仅向GCDin传递两个参数可reduce确保您的函数最多递归一次（因为len(numbers) > 2仅在原始调用中），这具有永远不会溢出堆栈的额外好处。

回答by torquestomp

The GCD operator is commutative and associative. This means that

GCD 算子是可交换和结合的。这意味着

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

So once you know how to do it for 2 numbers, you can do it for any number

所以一旦你知道如何对 2 个数字进行操作，你就可以对任何数字进行操作

---

---

To do it for two numbers, you simply need to implement Euclid's formula, which is simply:

要对两个数字执行此操作，您只需实现欧几里德公式，即：

// Ensure a >= b >= 1, flip a and b if necessary
while b > 0
  t = a % b
  a = b
  b = t
end
return a

Define that function as, say euclid(a,b). Then, you can define gcd(nums)as:

将该函数定义为，比如说euclid(a,b)。然后，您可以定义gcd(nums)为：

if (len(nums) == 1)
  return nums[1]
else
  return euclid(nums[1], gcd(nums[:2]))

This uses the associative property of gcd() to compute the answer

这使用 gcd() 的关联属性来计算答案

回答by Ashwini Chaudhary

You can use reduce:

您可以使用reduce：

>>> from fractions import gcd
>>> reduce(gcd,(30,40,60))
10

which is equivalent to;

相当于；

>>> lis = (30,40,60,70)
>>> res = gcd(*lis[:2])  #get the gcd of first two numbers
>>> for x in lis[2:]:    #now iterate over the list starting from the 3rd element
...    res = gcd(res,x)

>>> res
10

helpon reduce:

帮助上reduce：

>>> reduce?
Type:       builtin_function_or_method
reduce(function, sequence[, initial]) -> value

Apply a function of two arguments cumulatively to the items of a sequence,
from left to right, so as to reduce the sequence to a single value.
For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates
((((1+2)+3)+4)+5).  If initial is present, it is placed before the items
of the sequence in the calculation, and serves as a default when the
sequence is empty.

回答by Deepu

Try calling the GCD()as follows,

尝试调用GCD()如下，

i = 0
temp = numbers[i]
for i in range(len(numbers)-1):
        temp = GCD(numbers[i+1], temp)

回答by sarfarazit08

A solution to finding out the LCMof more than two numbers in PYTHONis as follow:

在PYTHON 中找出两个以上数字的LCM的解决方案如下：

#finding LCM (Least Common Multiple) of a series of numbers

def GCD(a, b):
    #Gives greatest common divisor using Euclid's Algorithm.
    while b:      
        a, b = b, a % b
    return a

def LCM(a, b):
    #gives lowest common multiple of two numbers
    return a * b // GCD(a, b)

def LCMM(*args):
    #gives LCM of a list of numbers passed as argument 
    return reduce(LCM, args)

Here I've added +1 in the last argument of range()function because the function itself starts from zero (0) to n-1. Click the hyperlink to know more about range()function :

这里我在range()函数的最后一个参数中添加了 +1，因为函数本身从零 (0) 到 n-1。单击超链接以了解有关range()函数的更多信息：

print ("LCM of numbers (1 to 5) : " + str(LCMM(*range(1, 5+1))))
print ("LCM of numbers (1 to 10) : " + str(LCMM(*range(1, 10+1))))
print (reduce(LCMM,(1,2,3,4,5)))

those who are new to python can read more about reduce()function by the given link.

那些不熟悉 Python 的人可以通过给定的链接阅读有关reduce()函数的更多信息。

回答by Zoe L

My way of solving it in Python. Hope it helps.

我在 Python 中解决它的方法。希望能帮助到你。

def find_gcd(arr):
    if len(arr) <= 1:
        return arr
    else:
        for i in range(len(arr)-1):
            a = arr[i]
            b = arr[i+1]
            while b:
                a, b = b, a%b
            arr[i+1] = a
        return a
def main(array):
    print(find_gcd(array))

main(array=[8, 18, 22, 24]) # 2
main(array=[8, 24]) # 8
main(array=[5]) # [5]
main(array=[]) # []

Some dynamics how I understand it:

我如何理解它的一些动态：

ex.[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

例如[8, 18] -> [18, 8] -> [8, 2] -> [2, 0]

18 = 8x + 2 = (2y)x + 2 = 2z where z = xy + 1

18 = 8x + 2 = (2y)x + 2 = 2z 其中 z = xy + 1

ex.[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

例如[18, 22] -> [22, 18] -> [18, 4] -> [4, 2] -> [2, 0]

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

22 = 18w + 4 = (4x+2)w + 4 = ((2y)x + 2)w + 2 = 2z

回答by Infinity

Python 3.9 introducedmultiple arguments version of math.gcd, so you can use:

Python 3.9引入了 的多参数版本math.gcd，因此您可以使用：

import math
math.gcd(30, 40, 36)

---

---

3.5 <= Python <= 3.8.x:

3.5 <= Python <= 3.8.x：

import functools
import math
functools.reduce(math.gcd, (30, 40, 36))

---

---

3 <= Python < 3.5:

3 <= Python < 3.5：

import fractions
import functools
functools.reduce(fractions.gcd, (30, 40, 36))