python不使用循环求最大公约数

Question

314·函数 main() 接收两个正整数 a、b 作为参数,计算并返回a和b的最大公约数。
例如,main（357,123）返回3,main（12,7）返回1。
不能使用循环结构,不能导入任何模块,不能有多余的输出。

最大公约数,也称最大公因数,指两个或多个整数共有约数中最大的一个。
a,b的最大公约数记为(a,b),同样的,a,b，c的最大公约数记为(a,b,c）,多个整数的最大公约数也有同样的记号。
求最大公约数有多种方法,常见的有质因数分解法,短除法,辗转相除法。
如6和12,6的因数有1,2,3,6;12的因数有1,2,3,4,6,12。它们最大公约数是6。

既然不能使用循环结构,那应当是不能使用辗转相除法了,而常规做法都是用到循环结构的。

ef main(a, b):
    #return a,b
    s1=[]
    s2=[]
    if a%2 == 0:
        s1.append(a)
    if b%2 == 0:
        s2.append(b)
    if max(s1) == (s2):
        return max(s1)

'''
答题错误！您的代码执行结果为：
None
None
Traceback (most recent call last):
  File xxx.py, line 14, in <module>
    print(main(357, 123))
  File xxx.py, line 9, in main
    if max(s1) == (s2):
ValueError: max() arg is an empty sequence
'''

现在关键是怎么列出每个参数的因数,然后两个最大值一比较就能做出来了。

Answer 1

最大公约数可以使用辗转相除法来求，如下代码实现：

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

输出

print(gcd(6, 12)) # 输出：6