求两个数m和n的最大公约数
时间: 2024-01-19 11:03:56 浏览: 41
首先,我们可以使用辗转相除法来求解两个数m和n的最大公约数。
步骤如下:
1. 用m除以n,得到商q和余数r。
2. 若r等于0,则n即为最大公约数。
3. 若r不等于0,则用n除以r,得到商q1和余数r1。
4. 若r1等于0,则r即为最大公约数。
5. 若r1不等于0,则重复步骤3和4,直到余数为0为止。
代码如下:
```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中较大的数作为被除数m,较小的数作为除数n,然后不断用被除数m除以除数n并求余数r,直到余数为0为止,最后被除数m即为最大公约数。
相关问题
Python求两个数m和n的最大公约数和最小公倍数
可以使用辗转相除法来求两个数的最大公约数,同时根据最大公约数和两个数的乘积可以求出最小公倍数。
以下是Python代码实现:
```python
def gcd(m, n):
"""
求最大公约数
"""
while n != 0:
m, n = n, m % n
return m
def lcm(m, n):
"""
求最小公倍数
"""
return m * n // gcd(m, n)
# 测试
print(gcd(24, 36)) # 输出 12
print(lcm(24, 36)) # 输出 72
```
其中,`gcd`函数使用了辗转相除法,不断将较大数除以较小数求余数,直到余数为0,此时较小数就是最大公约数。`lcm`函数则利用最大公约数和两个数的乘积来求最小公倍数。
求两个整数m和n的最大公约数
可以使用辗转相除法来求两个整数m和n的最大公约数,具体步骤如下:
1. 将m和n进行比较,如果m小于n,则交换m和n的值。
2. 用m除以n,得到余数r,如果r等于0,则n即为最大公约数;如果r不等于0,则将n赋值给m,将r赋值给n,然后重复执行步骤2,直到r等于0为止。
下面是一个求最大公约数的示例代码(使用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
```
其中,gcd函数接受两个整数m和n作为参数,返回它们的最大公约数。