python gcd算法

Python 中求两个数的最大公约数可以使用 math 模块中的 gcd 函数。例如：

import math

a = 15
b = 25
gcd = math.gcd(a, b)
print(gcd)  # 输出 5

如果不想使用 math 模块，也可以自己实现 gcd 算法。最常见的实现方式是使用辗转相除法，也叫欧几里得算法。其原理是：设 a、b 为两个正整数，gcd(a, b) 表示 a 和 b 的最大公约数，则有：

- 如果 a % b == 0，则 gcd(a, b) = b；
- 如果 a % b != 0，则 gcd(a, b) = gcd(b, a % b)。

根据这个递归定义，可以写出 Python 代码：

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

a = 15
b = 25
gcd_value = gcd(a, b)
print(gcd_value)  # 输出 5

这个函数首先判断 b 是否为 0，如果是，则 a 和 b 的最大公约数就是 a；否则，根据递归定义，将 b 和 a % b 的最大公约数作为结果返回。