Python求最大公约数(2)

qiuyouzhi

Python 求最大公约数

2，辗转相除法（欧几里得算法）

代码：

def gcdv2(a, b):
    big = a if a > b else b
    small = a if a < b else b
    if big % small == 0:
        return small
    return gcdv2(big%small, small) # 用递归实现辗转相除

print(gcdv2(25, 5))
print(gcdv2(100, 80))
print(gcdv2(27, 14))

• 辗转相除法
• 优点：常用，简洁
• 缺点：必须要取模
  

jackz007

       能否解释一下，为什么说 “必须要取模” 是 "缺点"？

zltzlt

代码可以简化

def gcdv2(a, b):
    if not (big := max(a, b)) % (small := min(a, b)):
        return small
    return gcdv2(big % small, small)  # 用递归实现辗转相除


print(gcdv2(25, 5))
print(gcdv2(100, 80))
print(gcdv2(27, 14))

一个账号

zltzlt 发表于 2020-3-5 12:36
代码可以简化

这只支持 3.8。

PS：我换头像了

zltzlt

一个账号 发表于 2020-3-5 12:42
这只支持 3.8。

PS：我换头像了

嗯

qiuyouzhi

jackz007 发表于 2020-3-5 12:32
能否解释一下，为什么说 “必须要取模” 是 "缺点"？

如果整数较大的话，取模运算性能会很差

qiuyouzhi

zltzlt 发表于 2020-3-5 12:36
代码可以简化

1，只支持3.8
2，写的稍微简单一点，用于理解

永恒的蓝色梦想

jackz007 发表于 2020-3-5 12:32
能否解释一下，为什么说 “必须要取模” 是 "缺点"？

取模效率不高

永恒的蓝色梦想

循环效率更好

def gcd(a,b):
    if a<b:
        a,b=b,a

    while b:
        a,b=b,a%b

    return a