使用辗转相除法和递归求两个正整数m和n的最大公约数。
时间: 2023-04-23 19:05:19 浏览: 151
用辗转相除法求最大公约数
使用辗转相除法和递归可以求出两个正整数m和n的最大公约数。
具体步骤如下:
1. 用m除以n,得到余数r。
2. 如果r等于,则n就是最大公约数。
3. 如果r不等于,则用n除以r,得到余数r1。
4. 重复步骤2和3,直到余数为为止。
5. 最后得到的n就是最大公约数。
递归实现的代码如下:
```python
def gcd(m, n):
if n == :
return m
else:
return gcd(n, m % n)
```
其中,第一行判断n是否为,如果是,则返回m;否则,执行第二行的递归调用,将n和m%n作为参数传入。这样,每次递归调用都会将n和m%n作为新的参数,直到n等于为止,返回最大公约数。
阅读全文