用python编写一个求最大公约数和最小公倍数的算法
时间: 2023-05-20 18:03:01 浏览: 70
可以使用辗转相除法来求最大公约数,同时利用最大公约数求最小公倍数。
代码如下:
```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)
```
其中,gcd 函数用于求最大公约数,lcm 函数用于求最小公倍数。
相关问题
用python写一个求最大公约数和最小公倍数的程序
下面是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)
# 测试代码
num1 = 12
num2 = 18
print("最大公约数为:", gcd(num1, num2))
print("最小公倍数为:", lcm(num1, num2))
```
在这个程序中,`gcd()`函数使用递归来计算两个整数的最大公约数,`lcm()`函数则调用`gcd()`函数来计算最小公倍数。测试代码中给定了两个整数`num1`和`num2`,并分别调用了`gcd()`和`lcm()`函数来计算它们的最大公约数和最小公倍数。
输出结果:
```
最大公约数为: 6
最小公倍数为: 36
```
因此,对于整数12和18,最大公约数是6,最小公倍数是36。
python编写函数求最大公约数和最小公倍数。
Python 编写函数求最大公约数和最小公倍数可以使用 Euclidean 算法。首先,根据两个数字a和b,计算它们的最大公约数gcd(a,b),其次利用最大公约数计算出它们的最小公倍数:lcm(a,b)=a*b/gcd(a,b)。