求两个数的最大公约数python 的代码解释
时间: 2024-02-04 20:08:51 浏览: 21
以下是求两个数的最大公约数的Python代码及解释:
```python
def gcd(a, b):
"""
求a和b的最大公约数
"""
while b:
a, b = b, a % b
return a
```
函数名为`gcd`,接收两个参数`a`和`b`,返回它们的最大公约数。
算法采用的是辗转相除法,也叫欧几里得算法。具体思路是不断用较小数去除以较大数,直到两个数中有一个数为0为止,此时另一个数就是最大公约数。
在代码中,我们使用了while循环,只要b不为0,就执行循环体中的语句。循环体中,先将a和b的值交换,再将a对b取模,将结果赋值给b。这个过程会一直重复,直到b为0,此时a的值就是最大公约数。最后将a返回即可。
例如,若要求72和42的最大公约数,调用`gcd(72, 42)`,执行过程如下:
1. a=72, b=42
2. b不为0,执行循环体
3. a=42, b=30
4. b不为0,执行循环体
5. a=30, b=12
6. b不为0,执行循环体
7. a=12, b=6
8. b不为0,执行循环体
9. a=6, b=0
10. b为0,退出循环
11. 返回a=6,即72和42的最大公约数为6。
相关问题
求两个数的最大公约数python代码
以下是求两个数的最大公约数的Python代码:
```python
def gcd(a, b):
while b:
a, b = b, a % b
return a
# 测试代码
print(gcd(24, 36)) # 输出 12
print(gcd(13, 169)) # 输出 13
```
其中,`gcd` 函数接收两个参数 `a` 和 `b`,通过欧几里得算法(又称辗转相除法)求出它们的最大公约数。在循环中,每次将 `a` 赋值为 `b`,将 `b` 赋值为 `a % b`,直到 `b` 为 0,此时 `a` 即为最大公约数。
求两个数最大公约数的代码用python
以下是求两个数最大公约数的 Python 代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
a = 24
b = 36
print("最大公约数:", gcd(a, b))
```
运行结果为:
```
最大公约数: 12
```
其中,`gcd` 函数采用了递归的方式实现求解。如果 `b` 等于 0,那么 `a` 就是最大公约数;否则,继续递归求解 `b` 和 `a % b` 的最大公约数。