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)

# 测试
print(gcd(12, 18)) # 输出6
print(gcd(25, 15)) # 输出5

这个函数的实现非常简单。如果 b 等于 0，那么 a 就是最大公约数。否则，我们需要用 a 除以 b 的余数来递归调用这个函数，直到 b 等于 0 为止。这个函数的时间复杂度是 O(log n)，其中 n 是 a 和 b 的最大值。

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

辗转相除法，也称欧几里得算法，是一种求解两个数的最大公约数的方法。在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)

# 示例
a = 1997
b = 615
print("最大公约数：", gcd(a, b))
print("最小公倍数：", lcm(a, b))