Python用辗转相除法求最大公约数

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

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

# 示例
print(gcd(24, 36))  # 输出：12

在这个函数中，我们使用递归的方式不断地进行辗转相除，直到余数为0，此时的被除数就是最大公约数。

相关问题

Python用辗转相除法求最大公约数，用fun函数

在Python中，可以使用欧几里得算法（也称为辗转相除法或更相减损术）来计算两个整数的最大公约数（Greatest Common Divisor, GCD）。这个算法基于数学原理：两个整数a和b（假设a > b），它们的最大公约数等于b和a mod b（即a除以b的余数）的最大公约数。如果b为0，则a就是最大公约数。

下面是一个名为`gcd`或`fun`的简单Python函数实现该算法：

def gcd(a, b):
    """
    使用辗转相除法计算两个数的最大公约数
    :param a: 整数，需要与b求最大公约数
    :param b: 整数，需要与a求最大公约数
    :return: a和b的最大公约数
    """
    while b != 0:
        a, b = b, a % b
    return a

# 示例
num1 = 48
num2 = 18
print(f"最大公约数: {gcd(num1, num2)}")

在这个例子中，如果你传入`gcd(48, 18)`，它会返回这两个数字的最大公约数，通常是6。

用python用辗转相除法求最大公约数与最小公倍数

可以使用以下代码来通过辗转相除法求最大公约数和最小公倍数：

# 定义函数求最大公约数
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

# 定义函数求最小公倍数
def lcm(a, b):
    return a * b // gcd(a, b)

# 例子：求 18 和 24 的最大公约数和最小公倍数
a = 18
b = 24
print("18 和 24 的最大公约数为：", gcd(a, b))
print("18 和 24 的最小公倍数为：", lcm(a, b))

输出结果为：

18 和 24 的最大公约数为： 6
18 和 24 的最小公倍数为： 72

这里用到了 Python 的整数除法运算符 `//`，它可以返回整数的商，即去掉小数部分的除法结果。