Python循环高效求解最大公约数：欧几里得算法详解

Python循环高效求解最大公约数：欧几里得算法详解

想要快速找到两个整数的最大公约数？欧几里得算法（辗转相除法）提供了一种优雅且高效的解决方案。以下是使用Python循环实现欧几里得算法的代码：

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

在这段代码中，我们使用while循环不断进行以下操作：

1. 计算a除以b的余数。
2. 将b的值赋给a，将余数赋给b。

循环持续进行，直到b的值变为0。此时，a的值即为原始两个整数的最大公约数。

代码解析：

• def gcd(a, b): 定义一个名为gcd的函数，接收两个整数a和b作为输入。
• while b != 0: 当b不等于0时，循环执行。
• a, b = b, a % b 使用Python的元组解包特性，同时完成两个赋值操作。
• return a 循环结束后，返回a的值，即最大公约数。

示例：

>>> gcd(24, 36)
12
>>> gcd(120, 80)
40

欧几里得算法是一种经典且高效的求解最大公约数的方法，使用Python循环实现该算法简洁易懂。希望本文能够帮助你理解并掌握这一算法。