欧几里得算法python

欧几里得算法，又称辗转相除法，是一种求两个整数的最大公约数的有效算法。该算法的基本思想是：两个整数a和b的最大公约数等于a除以b的余数r与b的最大公约数。这个过程可以重复执行，直到余数r等于0，此时b就是a和b的最大公约数。

以下是用Python实现欧几里得算法的示例代码：

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

# 测试
print(gcd(12, 8))  # 输出：4

在这个示例中，我们定义了一个函数gcd来计算两个数的最大公约数。使用while循环来重复计算a和b的余数r，并将b赋值为r，a赋值为原来的b，直到b等于0。最后返回a作为最大公约数。

相关问题

扩展欧几里得算法python

扩展欧几里得算法（Extended Euclidean Algorithm）也被称为扩展欧几里得定理，用于计算两个整数 a 和 b 的最大公约数（GCD）以及它们的贝祖等式的系数 x 和 y，满足以下等式：

ax + by = gcd(a, b)

以下是一个用 Python 实现的扩展欧几里得算法：

def extended_euclidean_algorithm(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x, y = extended_euclidean_algorithm(b % a, a)
        return gcd, y - (b // a) * x, x

这个函数接受两个整数 a 和 b 作为输入，返回它们的最大公约数 gcd 以及 x 和 y 的值，它们满足贝祖等式。如果 a 是 0，那么 gcd 等于 b，此时 x 等于 0，y 等于 1。否则，递归调用函数，计算 b 对 a 取模的结果和 a 之间的 GCD，同时计算 x 和 y 的值。

下面是一个示例，演示如何使用扩展欧几里得算法来计算 35 和 15 的最大公约数以及它们的贝祖等式的系数：

gcd, x, y = extended_euclidean_algorithm(35, 15)
print("gcd(35, 15) = {}".format(gcd))
print("x = {}, y = {}".format(x, y))

输出：

gcd(35, 15) = 5
x = 1, y = -2

因此，35 和 15 的最大公约数是 5，它们的贝祖等式为 1 x 35 + (-2) x 15 = 5。

欧几里得算法Python公式

欧几里得算法（又称辗转相除法）是求最大公约数的算法，其 Python 公式如下：

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

其中 `a` 和 `b` 是要求最大公约数的两个数。这个函数会一直递归调用，直到 `b` 等于 0，此时 `a` 就是最大公约数。