Python习题 142：两个正整数的最大公约数

说明

《Python 教程》持续更新中，提供建议、纠错、催更等加作者微信: gairuo123（备注：pandas教程）和关注公众号「盖若」ID: gairuo。跟作者学习，请进入 Python学习课程。欢迎关注作者出版的书籍：《深入浅出Pandas》和《Python之光》。

（编码题）编写 Python 函数，求两个正整数的最大公约数。

最大公约数即为Greatest Common Divisor，常缩写为gcd。一组整数的公约数，是指同时是这组数中每一个数的约数的数。是任意一组整数的公约数。一组整数的最大公约数，是指所有公约数里面最大的一个。a 和 b 的GCD通常表示为 gcd(a, b)。

参考代码

代码如下：

# 定义一个函数来计算两个数字的最大公约数。
def gcd(x, y):
    # 将gcd初始化为1
    gcd = 1

    # 检查y是否是x的除数（x可被y整除）
    if x % y == 0:
        return y

    # 从y的一半迭代到1
    for k in range(int(y / 2), 0, -1):
        # 检查x和y是否都可以被k整除
        if x % k == 0 and y % k == 0:
            # 将GCD更新为当前值k并退出循环
            gcd = k
            break

    # 返回计算出的 GCD
    return gcd

# 打印特定数字对的 GCD
print("12 & 17 =", gcd(12, 17))
print("4 & 6 =", gcd(4, 6))
print("336 & 360 =", gcd(336, 360))
'''
12 & 17 = 1
4 & 6 = 2
336 & 360 = 24
'''

欧几里德算法

代码如下：

def gcd(x, y):
    return x if y == 0 else gcd(y, x%y)

print("12 & 17 =", gcd(12, 17))
print("4 & 6 =", gcd(4, 6))
print("336 & 360 =", gcd(336, 360))
'''
12 & 17 = 1
4 & 6 = 2
336 & 360 = 24
'''

这是一个计算两个整数的最大公约数（GCD）的函数，使用的是欧几里德算法，也称为辗转相除法。下面是对代码的详细解释：

gcd 是函数的名称，表示最大公约数（Greatest Common Divisor）。
x 和 y 是函数的两个参数，代表要计算最大公约数的两个整数。
return x if y == 0 else gcd(y, x % y) 是一个三元条件表达式，它实现了欧几里德算法的递归定义。

代码逻辑解释：

如果 y 等于 0，意味着 x 就是最大公约数，因此返回 x。
否则，调用 gcd(y, x % y)，这里是递归调用。在欧几里德算法中，每一步都用较小的数去除以较大的数，直到较小的数为 0。最终，最大的非零余数就是最大公约数。

这个算法的核心思想是不断地用较小的数去除以较大的数，直到余数为 0。最后的非零余数就是最大公约数。这种递归实现方式很优雅，而且算法效率较高。

解析

可按以下思路减少循环次数：

当最小值为最大公约数时，直接返回；
当最小值不为最大公约数时，最大公约数不会大于最小值的1/2；
求最大公约数理应从大到小循环递减求最大。

（完）

Python习题 142：两个正整数的最大公约数

参考代码

欧几里德算法

解析

相关内容