Python求列表最大公约数

Question

我想计算一组数字的最大公约数，但是我不知道我的代码哪里出了问题。

A = [12, 24, 27, 30, 36]


def Greatest_Common_Divisor(A):
    for c in A:
        while int(c) > 0:
            if int(c) > 12:
                c = int(c) % 12
            else:
                return 12 % int(c)
    print Greatest_Common_Divisor(A)

- redmouse

---

寻求调试帮助的问题（“为什么这段代码不起作用？”）必须在问题本身中包含所需的行为、具体问题或错误以及重现它所需的最短代码。没有明确问题陈述的问题对其他读者没有用处。 - thefourtheye

这个问题表明在Python标准库中已经实现了最大公约数。只需使用“from fractions import gcd”。 - Kyle_S-C

另外，一旦执行了return 12％int（c）语句，函数就会结束。您是否想使用生成器？ - Kyle_S-C

Answer 1

这是我使用的代码片段：

from fractions import gcd
from functools import reduce
def find_gcd(list):
    x = reduce(gcd, list)
    return x

- Ayoub ABOUNAKIF

---

我收到了一个警告，说 fractions.gcd 已经被弃用了，现在建议使用 math.gcd。 - kevin_theinfinityfund

在 Python 3 中，使用 from math import gcd 来导入最大公约数函数。 - shahar_m

Answer 2

从Python 3.9开始，Python内置了对一组数字计算最大公约数的支持。

import math
A = [12, 24, 27, 30, 36]
print(math.gcd(*A))

输出：

3

- bigbounty

Answer 3

def gcd (a,b):
    if (b == 0):
        return a
    else:
         return gcd (b, a % b)
A = [12, 24, 27, 30, 36]
res = A[0]
for c in A[1::]:
    res = gcd(res , c)
print res

ideone链接

- Pankaj Kumar

Answer 4

我使用了以下这段代码：

def gcd(my_list):
    result = my_list[0]
    for x in my_list[1:]:
        if result < x:
            temp = result
            result = x
            x = temp
        while x != 0:
            temp = x
            x = result % x
            result = temp
    return result 

- kourosh

Answer 5

如果您想使用现有的方法，请尝试`np.gcd.reduce'：

import numpy as np

A = [12, 24, 27, 30, 36]

print(np.gcd.reduce(A))

这将返回3

- uhoh

---

当列表长度>100000时，它会给出WA。 - DikShU

@DikShU 告诉我们更多！对我来说，当长度为1,000,000时，np.gcd.reduce((6060842*np.random.rint(1, 10000000, 1000000)).tolist()) 使用numpy 1.19.2 返回 6060842。你所说的测试是什么？你使用的是哪个版本的numpy？还有哪些gcd方法通过了你的测试，而这个失败了呢？ - uhoh

我正在Codechef（印度的CP网站）上使用它，在长度小于1000的测试用例中它可以通过，但在原始约束条件下会出现WA。 - DikShU

@DikShU 我明白了，“WA”是指错误答案。我已经访问了该网站并尝试运行它https://i.stack.imgur.com/5iHu7.png，但我无法导入`numpy` https://i.stack.imgur.com/Mi4fu.png 因此，我甚至无法在那里进行测试。我不确定Python在网站上如何运行，但在计算机上本地运行似乎是可以的。我不确定你为什么会得到“WA”，但这似乎与Codechef有关，这不是Python消息。顺便说一下，我的原始代码有一个打字错误，应该是 np.random.randint而不是 ...rint。 - uhoh

在 Codechef 上运行 Python，请将代码放在 try 和 except 语句块中，并感谢帮助...这可能是 WA 的其他原因。更多问题请参见："https://www.codechef.com/JULY21C/problems/MINNOTES" - DikShU

Answer 6

我不太清楚你在函数中为什么使用了12？你是否想特别测试一下12的算法？

有一个内置函数可以提供很好的解决方案（fraction.gcd()），可以参考这个答案。

如果你想开发自己的方法，可以这样做：对列表进行排序并获取列表中的最小数（称其为min）。从2到min循环，就可以得到列表的最大公约数。

- edwardramsey

Answer 7

import functools as f
A = [12, 24, 27, 30, 36]
g = lambda a,b:a if b==0 else g(b,a%b)   #Gcd for two numbers
print(f.reduce(lambda x,y:g(x,y),A))     #Calling gcd function throughout the list.

"Lambda"是一个匿名函数，每次调用时都会将'g'赋值为两个数字的最大公约数。

"Reduce"是“functools”模块中的一个函数，它用于对列表中的所有元素执行特定的功能。在这里，reduce()通过计算前两个元素的最大公约数，然后计算第三个元素与先前计算的前两个元素的最大公约数等来计算完整列表A的最大公约数。

希望这能解决您的疑问。

- kateshdrops

---

从评论中：您能否添加更多的解释，说明为什么这个解决方案可以解决问题？ - toti08

嘿，是的，我已经添加了更多关于如何解决问题的说明。 - kateshdrops

Answer 8

我看到你的代码会进入无限循环。因为你递归调用了Greatest_Common_Divisor方法，但没有基本情况。将print Greatest_Common_Divisor(A)和“def”对齐，这个问题就会解决。但是你的代码对于每个数字ai做什么，它取模ai % 12的余数，然后简单地打印12 % (ai % 12)，它和最大公约数之间没有任何联系。这里是gcd(a,b)的简单代码，你可以用于整个数组：

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

- Mamuka

Answer 9

from functools import reduce
def gcd(a,b):
    if a==0:
        return b 
    else:
        return gcd(b%a,a)
A = [12, 24, 27, 30, 36]
gcdp = reduce(lambda x,y:gcd(x,y),A)
print(gcdp)

我猜这个会解决你的疑惑。

- Anonymous

Answer 10

return 语句用于退出函数。在 for 循环中，通常不打算使用该语句。

- Daniel