用Python求两个正整数的最大公约数
时间: 2024-03-28 08:14:52 浏览: 9
可以使用欧几里得算法(又称辗转相除法)来求两个正整数的最大公约数。
代码如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 测试
a = 48
b = 60
print(gcd(a, b)) # 输出 12
```
在这个代码中,我们定义了一个函数 `gcd`,它接受两个参数 `a` 和 `b`,返回它们的最大公约数。在函数内部,我们使用递归的方式来实现欧几里得算法。如果 `b` 等于0,那么 `a` 就是最大公约数;否则,我们将 `b` 和 `a` 对 `b` 取模后的结果作为新的参数传入递归调用。
最后,我们测试了一下这个函数,求出了48和60的最大公约数,结果是12。
相关问题
用python求两个正整数的最大公约数
可以使用欧几里得算法来求两个正整数的最大公约数。代码实现如下:
```python
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
```
其中,a和b分别为两个正整数。可以通过调用这个函数来求它们的最大公约数。
python求两个正整数的最大公约数和最小公倍数
最大公约数(GCD)是两个或多个整数的最大公因数,最小公倍数(LCM)是两个或多个整数的最小公倍数。
求两个正整数的最大公约数可以使用欧几里得算法,也称为辗转相除法。该算法的基本思想是,用较小的数除以较大的数,将余数作为新的被除数,原来的除数作为新的除数,重复这个过程,直到余数为,此时除数就是最大公约数。
求两个正整数的最小公倍数可以使用最大公约数来计算。最小公倍数等于两个数的乘积除以它们的最大公约数。
例如,对于正整数12和18,它们的最大公约数是6,最小公倍数是36。