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

以下是使用辗转相除法求最大公约数的Python代码：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

x = eval(input("请输入两个整数:"))
print("最大公约数为:", gcd(max(x), min(x)))

在这个代码中，我们定义了一个名为`gcd`的函数，它接受两个参数`a`和`b`，并返回它们的最大公约数。在函数中，我们使用了while循环来实现辗转相除法，直到余数为0时停止循环，此时的被除数即为最大公约数。在主程序中，我们通过`max`和`min`函数来获取输入的两个整数的最大值和最小值，并将它们作为参数传递给`gcd`函数来求解最大公约数。

相关问题

python辗转相除法求最大公约数和循坏次数

以下是使用Python实现辗转相除法求最大公约数和循环次数的代码：

def gcd(a, b):
    count = 0
    while b != 0:
        count += 1
        a, b = b, a % b
    return a, count

其中，a和b分别为要求最大公约数的两个数，count记录循环次数。

例如，求50和15的最大公约数，可以使用以下代码：

a, count = gcd(50, 15)
print("最大公约数为：", a)
print("循环次数为：", count)

输出结果为：

最大公约数为： 5
循环次数为： 3

说明辗转相除法需要循环3次才能求出50和15的最大公约数为5。

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

Python中的辗转相除法可以用以下代码实现：

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

其中，`gcd`函数用于求最大公约数，`lcm`函数用于求最小公倍数。

辗转相除法的基本思想是：用较大的数除以较小的数，再用余数去除较小的数，如此反复，直到余数为为止。最后的除数就是最大公约数，而最小公倍数等于两数之积除以最大公约数。

例如，求出30和45的最大公约数和最小公倍数，可以这样调用函数：

>>> gcd(30, 45)
15
>>> lcm(30, 45)
90

因此，30和45的最大公约数是15，最小公倍数是90。