Python求最大公约数的几种方法（1）

qiuyouzhi

Python求最大公约数

1，暴力枚举算法

思路：
从较小整数的一半开始，尝试找到一个合适的整数，看它能否被a,b同时整除
代码：

def gcd(a, b):
    big = a if a > b else b
    small = a if a < b else b
    if big % small == 0:
        return small

    for i in range(small // 2, 2, -1):
        if small % i == 0 and big % i == 0:
            return i
        
    return 1

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

• 暴力枚举
• 优点：思路简单
• 缺点：效率太慢，如果传入数据是10000和10001，就要计算10000/2-1=4999次
  

后面会继续更新！

一个账号

我的方法：

def gcd(x, y):
    while x != 0:
        x, y = y % x, x
    return y

TJBEST

一个账号 发表于 2020-3-5 10:41
我的方法：

负数也行吗？

永恒的蓝色梦想

我的方法：

from math import gcd

qiuyouzhi

永恒的蓝色梦想 发表于 2020-3-5 11:19
我的方法：

这个方法也会提到
但是先用手写的