用python求两个正整数m, n的最大公约数
时间: 2024-05-01 07:19:01 浏览: 13
可以使用欧几里得算法(辗转相除法)来求解两个正整数的最大公约数。
代码如下:
```python
def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m % n)
```
其中,如果n等于0,则m就是最大公约数;否则,递归调用gcd函数,将n和m%n作为参数继续求解。
例如,求解24和36的最大公约数:
```python
>>> gcd(24, 36)
12
```
因此,24和36的最大公约数是12。
相关问题
python求两个正整数m和n的最大公约数
你好!感谢使用ChitGPT进行对话。关于你的问题,求两个正整数m和n的最大公约数,可以使用辗转相除法,也称为欧几里德算法,求解。具体步骤如下:
1. 如果m小于n,则交换m和n。
2. 用m除以n,得到余数r。
3. 如果r等于0,则n就是最大公约数。
4. 如果r不等于0,则让m等于n,n等于r,返回步骤2。
下面是使用Python实现辗转相除法的代码:
```python
def gcd(m, n):
if m < n:
m, n = n, m
while n != 0:
r = m % n
m = n
n = r
return m
```
你可以调用这个函数,传入你想要求最大公约数的两个正整数m和n,它将返回它们的最大公约数。希望这个答案能够帮助到你。
用Python求两个正整数的最大公约数
可以使用欧几里得算法(又称辗转相除法)来求两个正整数的最大公约数。
代码如下:
```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。