Python求用辗转相除法求最大公约数和最小公倍数
时间: 2024-09-30 16:00:51 浏览: 12
Python中可以使用辗转相除法(也叫欧几里得算法)来计算两个整数的最大公约数(Greatest Common Divisor,简称GCD)。这是一种通过不断将较大的数除以较小的数,然后用余数替换较大数,直到余数为0为止,此时的较小数就是两数的最大公约数。
以下是一个简单的Python函数示例:
```python
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# 示例
print(gcd(48, 18)) # 输出:6
```
对于求最小公倍数(Least Common Multiple,简称LCM),通常有以下公式:`lcm(a, b) = abs(a * b) // gcd(a, b)`。这是因为两个数的乘积等于它们的最大公约数和最小公倍数的乘积。
下面是计算最小公倍数的函数:
```python
def lcm(a, b):
return abs(a * b) // gcd(a, b)
# 示例
print(lcm(48, 18)) # 输出:144
```
相关问题
用python写代码求最小公倍数,要求用辗转相除法先求最大公约数再求最小公倍数
以下是使用 Python 实现辗转相除法求解最小公倍数的代码:
```python
def gcd(a, b):
"""
辗转相除法求最大公约数
"""
while b:
a, b = b, a % b
return a
def lcm(a, b):
"""
求最小公倍数
"""
return a * b // gcd(a, b)
```
这里我们定义了两个函数,`gcd()` 用于求解最大公约数,`lcm()` 用于求解最小公倍数。在 `gcd()` 函数中,我们使用辗转相除法求解最大公约数。在 `lcm()` 函数中,我们先调用 `gcd()` 函数求出两个数的最大公约数,然后将两个数相乘除以最大公约数得到最小公倍数。
下面是一个例子,演示如何使用这两个函数来求解最小公倍数:
```python
a = 36
b = 48
print(f"最小公倍数为 {lcm(a, b)}")
```
输出结果为:
```
最小公倍数为 144
```
即 36 和 48 的最小公倍数为 144。
用python用辗转相除法求最大公约数与最小公倍数
可以使用以下代码来通过辗转相除法求最大公约数和最小公倍数:
```python
# 定义函数求最大公约数
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 定义函数求最小公倍数
def lcm(a, b):
return a * b // gcd(a, b)
# 例子:求 18 和 24 的最大公约数和最小公倍数
a = 18
b = 24
print("18 和 24 的最大公约数为:", gcd(a, b))
print("18 和 24 的最小公倍数为:", lcm(a, b))
```
输出结果为:
```
18 和 24 的最大公约数为: 6
18 和 24 的最小公倍数为: 72
```
这里用到了 Python 的整数除法运算符 `//`,它可以返回整数的商,即去掉小数部分的除法结果。