欧几里德算法python

欧几里德算法，也称为辗转相除，是用于计算两个非负数的最大公约数（GCD）的一种方法。下面是一个用Python实现欧几德算法的示例：

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

# 示例用法
num1 48
num2 = 36
gcd euclidean_algorithm(num1, num2)
print("最大公约数为:", gcd)

这段代码中`euclidean_algorithm`函数接受两个整数作为参数，并使用while循环来迭计算最大约数。在每次迭代中，将`b`赋值给`a`，将`a % b`的结果赋值给`b`，直到`b`为0时停止循环。最后返回的`a`即为最大公约数。

相关问题

扩展欧几里德算法求模逆元

扩展欧几里德算法是求解一元一次不定方程 ax+by=gcd(a,b) 的算法，其中 a, b 为整数，x, y 为整数解，gcd(a,b) 表示 a 和 b 的最大公约数。在求解模逆元的问题中，我们需要求解的是 ax ≡ 1 (mod n) 的解 x，其中 n 是模数，也是一个整数。

为了使用扩展欧几里德算法求解模逆元，我们需要将上述一元一次不定方程转化为 ax+ny=1 的形式。这里 n 就是模数，因为 ax ≡ 1 (mod n) 等价于 ax-ny=1，所以我们需要找到 a 和 n 的最大公约数 gcd(a,n)，如果 gcd(a,n) 不为 1，则方程无解；否则，我们就可以使用扩展欧几里德算法求解出 ax+ny=1 的一组整数解，其中 x 就是 a 在模 n 意义下的逆元。

下面是求解模逆元的 Python 代码实现：

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ext_gcd(b, a % b)
        return d, y, x - (a // b) * y
 
def mod_inverse(a, n):
    d, x, y = ext_gcd(a, n)
    if d != 1:
        return None  # a 和 n 不互质，不存在模逆元
    else:
        return (x % n + n) % n  # 返回 a 在模 n 意义下的逆元

其中，`ext_gcd(a, b)` 函数用于求解一元一次不定方程 ax+by=gcd(a,b) 的整数解 (x, y) 和 gcd(a,b)。`mod_inverse(a, n)` 函数则是利用扩展欧几里德算法求解模逆元的函数，如果 a 和 n 不互质，即 gcd(a,n) != 1，则返回 `None` 表示不存在模逆元；否则，返回 a 在模 n 意义下的逆元 `(x % n + n) % n`。

求最大公约数的欧几里德算法

欧几里德算法，也称辗转相除法，用于求两个正整数的最大公约数（GCD）。算法基于下面的定理：

对于任何整数a和b，它们的最大公约数等于a除以b的余数r和b之间的最大公约数。

算法步骤如下：

1. 如果a小于b，则交换a和b。

2. 用a除以b，得到余数r。

3. 如果r为0，则b是最大公约数。

4. 否则，将b赋值为r，然后返回第二步。

下面是一个Python实现：

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

例如，gcd(60, 48)将返回12，因为60和48的最大公约数是12。