python中辗转相除法
时间: 2023-11-06 13:18:08 浏览: 59
辗转相除法,也称欧几里得算法,是求两个整数的最大公约数的常用方法之一。
Python 中可以使用递归实现辗转相除法,代码如下:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,a 和 b 分别为两个整数,当 b 等于 0 时,a 即为最大公约数;当 b 不等于 0 时,递归调用 gcd 函数,传入参数为 b 和 a 除以 b 的余数(即 a mod b)。
例如,求 24 和 60 的最大公约数,可以调用 gcd(24, 60),得到结果为 12。
相关问题
python中辗转相除法求最大公约数
辗转相除法是求解两个数的最大公约数的一种方法,也叫欧几里得算法。
在Python中,可以使用如下代码实现辗转相除法:
```
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,a和b为要求最大公约数的两个数。递归调用gcd函数,直到b为0,此时a就是最大公约数。
例如,要求48和60的最大公约数,可以这样调用gcd函数:
```
print(gcd(48, 60))
```
输出结果为12,即48和60的最大公约数为12。
python用辗转相除法
辗转相除法(又称欧几里得算法)是一种求两个正整数最大公约数的算法。在Python中,可以使用递归实现辗转相除法。下面是一个示例代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
a = 36
b = 48
result = gcd(a, b)
print("最大公约数为:", result)
```
这段代码中,`gcd`函数接收两个参数a和b,通过递归调用实现辗转相除法。当b等于0时,即找到了最大公约数,将其返回。运行以上代码,输出结果为`最大公约数为: 12`。