python 欧几里得算法

欧几里得算法，也称为辗转相除法，用于求两个非负整数的最大公约数（Greatest Common Divisor，简称GCD）。在Python中，可以使用递归或循环来实现欧几里得算法。以下是一个示例：

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

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

这段代码中，`euclidean_algorithm` 函数使用了递归来实现欧几里得算法。首先判断 `b` 是否为0，若是，则返回 `a` 作为最大公约数；否则，继续递归调用函数，并将 `b` 作为新的 `a`，`a % b` 作为新的 `b`。通过不断取两数的余数直至其中一个数为0，最后返回的非零数即为最大公约数。

在上面的示例中，输入的数字分别是48和36，它们的最大公约数为12。

相关问题

python欧几里得算法

欧几里得算法是一种求解两个整数的最大公约数的方法。在Python中，可以使用递归实现欧几里得算法，代码如下所示：

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

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

通过调用该函数，可以得到12和8的最大公约数，即4。

python欧几里得算法最大公因子

欧几里得算法（辗转相除法）是一种用于求解两个整数的最大公因子的算法。根据引用[1]，给定两个整数a和b，我们可以使用欧几里得算法来计算它们的最大公因子。具体步骤如下：

1. 首先，将较大的数赋值给变量a，将较小的数赋值给变量b。
2. 使用辗转相除法，计算a除以b的余数，并将余数赋值给变量r。
3. 如果r等于0，表示b是a的最大公因子，算法结束。
4. 如果r不等于0，将b的值赋值给a，将r的值赋值给b，然后返回第2步继续计算。

根据引用和引用，以下是使用Python实现欧几里得算法求解最大公因子的示例代码：

# 递归实现
def gcd_recursive(a, b):
    if b == 0:
        return a
    else:
        return gcd_recursive(b, a % b)

# 非递归实现
def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 使用示例
a = 24
b = 36
gcd = gcd_recursive(a, b)
print("最大公因子为:", gcd)