### 实现原理 辗转相除法（又称欧几里得算法）是一种高效求解两个正整数最大公约数的方法。其核心思想是：用较大的数除以较小的数，然后用余数继续这一过程，直到余数为0，此时的除数即为两个数的最大公约数。该方法不需要对数字进行质因子分解，因此在计算效率上具有明显优势[^2]。 --- ### Python 实现代码 以下是一个完整的 Python 实现示例，用于计算两个正整数的最大公约数： ```python def gcd(a, b): while b != 0: a, b = b, a % b return a # 示例输入 x = int(input("请输入第一个整数：")) y = int(input("请输入第二个整数：")) result = gcd(x, y) print(f"{x} 和 {y} 的最大公约数是：{result}") ``` 该实现通过循环不断更新被除数和除数，直到余数为0，最终返回最大公约数。 --- ### 扩展功能：计算最小公倍数 在获得最大公约数后，可以通过以下公式计算两个数的最小公倍数： $$ \text{最小公倍数} = \frac{a \times b}{\text{最大公约数}(a, b)} $$ 基于上述代码，可以扩展功能以同时输出最大公约数和最小公倍数： ```python def gcd_and_lcm(a, b): gcd_value = a while b != 0: gcd_value, b = b, gcd_value % b lcm_value = a * b // gcd_value return gcd_value, lcm_value # 示例输入 x = int(input("请输入第一个整数：")) y = int(input("请输入第二个整数：")) gcd_result, lcm_result = gcd_and_lcm(x, y) print(f"{x} 和 {y} 的最大公约数是：{gcd_result}") print(f"{x} 和 {y} 的最小公倍数是：{lcm_result}") ``` 该代码通过 `gcd_and_lcm` 函数同时返回最大公约数和最小公倍数，避免重复计算[^3]。 --- ### 性能与适用性 辗转相除法的时间复杂度为 $O(\log \min(a, b))$，适用于大整数的快速计算。由于其算法逻辑简单且效率高，广泛应用于密码学、数据压缩、数论等领域。 --- ### 相关问题