求两个数的最大公约数Python
时间: 2023-09-26 15:09:21 浏览: 113
可以使用辗转相除法(欧几里得算法)来求两个数的最大公约数。
辗转相除法的基本思路是:设两数为 a、b(a > b),将 a 除以 b,得到余数 c,若 c=0,则 b 即为最大公约数;否则,b 和 c 继续执行上述操作,直到余数为 0。
以下是使用 Python 实现辗转相除法求两个数的最大公约数的代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 示例
print(gcd(24, 36)) # 输出:12
```
在上面的代码中,`gcd()` 函数接受两个参数 `a` 和 `b`,如果 `b` 等于 0,则返回 `a`,否则返回 `gcd(b, a % b)`,其中 `a % b` 表示 a 除以 b 的余数。这样就能实现递归调用,直到 b 等于 0 时返回最大公约数 a。
相关问题
求两个数的最大公约数python
可以使用辗转相除法(欧几里得算法)来求两个数的最大公约数。
辗转相除法的基本思路是:设两数为 a、b(a > b),将 a 除以 b,得到余数 c,若 c=0,则 b 即为最大公约数;否则,b 和 c 继续执行上述操作,直到余数为 0。
以下是使用 Python 实现辗转相除法求两个数的最大公约数的代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 示例
print(gcd(24, 36)) # 输出:12
```
在上面的代码中,`gcd()` 函数接受两个参数 `a` 和 `b`,如果 `b` 等于 0,则返回 `a`,否则返回 `gcd(b, a % b)`,其中 `a % b` 表示 a 除以 b 的余数。这样就能实现递归调用,直到 b 等于 0 时返回最大公约数 a。
求两个数的最大公约数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` 即为最大公约数。
阅读全文