python计算最大公约数和最小公倍数
时间: 2023-10-25 09:08:43 浏览: 54
可以使用Python中的math库中的gcd函数计算最大公约数,和lcm函数计算最小公倍数。例如:
```python
import math
num1 = 24
num2 = 36
gcd = math.gcd(num1, num2)
lcm = num1*num2//gcd
print("最大公约数为:", gcd)
print("最小公倍数为:", lcm)
```
输出结果为:
```
最大公约数为: 12
最小公倍数为: 72
```
希望可以帮到您。
相关问题
如何用Python计算最大公约数和最小公倍数
两个数的最大公约数可以用 Euclidean algorithm 来计算,Python 中实现方式如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
最小公倍数可以用最大公约数来计算,公式为 `lcm(a, b) = a * b / gcd(a, b)`,Python 中实现方式如下:
```python
def lcm(a, b):
return a * b / gcd(a, b)
```
使用示例:
```python
a = 12
b = 18
print("最大公约数:", gcd(a, b))
print("最小公倍数:", lcm(a, b))
```
Python最大公约数和最小公倍数计算
最大公约数和最小公倍数的计算可以使用多种方法。其中包括穷举法、辗转相减法和更相减损法等。下面是三种常见的计算方法:
方法一:穷举法
给定两个正整数a和b,首先判断它们是否都是偶数。如果是,就用2约简;如果不是,则执行第二步。以较大的数减去较小的数,然后将所得的差与较小的数比较,并以较大数减去较小数。继续这个操作,直到所得的减数和差相等为止。最后,第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。同时,最小公倍数可以通过两个数的乘积除以最大公约数来得到。
方法二:辗转相减法
给定两个正整数a和b,首先比较它们的大小,将较大的数赋值给a,将较小的数赋值给b。然后,用a除以b得到余数r,将b赋值给a,将r赋值给b。再次执行这个操作,直到余数r为0为止。此时,最大公约数就是非零的b,最小公倍数可以通过两个数的乘积除以最大公约数来得到。
方法三:更相减损法
给定两个正整数a和b,如果a和b都是偶数,就用2约简,然后更新a和b。如果不是偶数,就执行第二步。以较大的数减去较小的数,然后将所得的差与较小的数比较,并以较大数减去较小数。继续这个操作,直到所得的减数和差相等为止。最后,第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。同时,最小公倍数可以通过两个数的乘积除以最大公约数来得到。