首页python 递归求最大公约数和最小公倍数

python 递归求最大公约数和最小公倍数

时间: 2025-05-19 18:22:40 浏览: 43

### Python 实现递归求解最大公约数和最小公倍数以下是基于递归方法实现的最大公约数（GCD）和最小公倍数（LCM）的 Python 函数： #### 最大公约数（GCD）欧几里得算法是一种经典的递归方法用于计算两个整数的最大公约数。其核心思想是反复利用余数运算，直到其中一个参数变为零。 ```python def RecursiveGcd(x, y): if y == 0: return x else: return RecursiveGcd(y, x % y) ``` 上述代码实现了递归版本的 GCD 计算逻辑[^1]。当 `y` 变为零时，返回当前的 `x` 值作为结果；否则继续调用自身并传入 `(y, x % y)` 参数组合。 #### 最小公倍数（LCM）最小公倍数可以通过以下公式与最大公约数关联起来： \[ \text{lcm}(x, y) = \frac{|x \cdot y|}{\text{gcd}(x, y)} \] 因此，在已知递归版 GCD 的基础上可以轻松定义 LCM 函数如下所示： ```python def computeLcmWithRecursiveGcd(x, y): lcm = abs(x * y) // RecursiveGcd(x, y) return lcm ``` 此部分代码展示了如何通过调用先前定义好的递归 GCD 方法来完成 LCM 的计算过程[^3]。综合以上两部分内容，完整的程序结构应如下所列： ```python def RecursiveGcd(x, y): if y == 0: return x else: return RecursiveGcd(y, x % y) def computeLcmWithRecursiveGcd(x, y): lcm = abs(x * y) // RecursiveGcd(x, y) return lcm # 输入测试数据 if __name__ == "__main__": a = int(input()) b = int(input()) # 输出结果 print(computeLcmWithRecursiveGcd(a, b)) ``` 该脚本首先接收用户输入的一对正整数值，随后打印它们对应的最小公倍数。 --- 问题

阅读全文