输入两个正整数m n求其最大公约数
时间: 2024-03-24 18:32:30 浏览: 20
以下是两种求最大公约数的方法:
1.辗转相除法
```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 = int(input("请输入第一个正整数:"))
= int(input("请输入第二个正整数:"))
print("最大公约数为:", gcd(m, n))
```
2.更相减损法
```python
def gcd(m, n):
if m < n:
m, n = n, m
while m != n:
r = m - n
m = max(r, n)
n = min(r, n)
return m
m = int(input("请输入第一个正整数:"))
n = int(input("请输入第二个正整数:"))
print("最大公约数为:", gcd(m, n))
```
相关问题
输入两个正整数m n 求其最大公倍数和最小公约数
好的,您输入的两个正整数分别为m和n,我来回答您的问题:
首先,最大公倍数(简称最大公约数)是指能同时整除m和n的最大正整数。可以通过辗转相除法来求得最大公约数,具体步骤如下:
1. 用较大的数除以较小的数,得到余数
2. 用上一步得到的余数去除较小的数,再得到余数
3. 重复上一步,直到余数为0,此时较小的数即为最大公约数
其次,最小公倍数是指m和n的公共倍数中最小的那个数。可以通过以下公式来求得最小公倍数:
最小公倍数 = m * n / 最大公约数
因此,根据上述方法,m和n的最大公约数为x,最小公倍数为y,则有:
x = (m,n)
y = m * n / x
希望能够帮助您解决问题,如果您还有其他问题,请继续提问。
输入两个正整数m和n,求其最大公约数
输入两个正整数m和n,求它们的最大公约数可以使用辗转相除法。具体步骤如下:
1. 用较小的数除以较大的数,得到余数r。
2. 如果r等于0,则较大的数即为最大公约数。
3. 如果r不等于0,则用较小的数除以r,得到余数r1。
4. 如果r1等于0,则r即为最大公约数。
5. 如果r1不等于0,则继续用r除以r1,得到余数r2。
6. 重复以上步骤,直到余数为0为止,最后的除数即为最大公约数。
下面是一个C语言程序的例子,可以实现输入两个正整数m和n,求它们的最大公约数:
```
#include <stdio.h>
int main()
{
int m, n, r;
printf("请输入两个正整数:");
scanf("%d%d", &m, &n);
while (n != 0)
{
r = m % n;
m = n;
n = r;
}
printf("最大公约数为:%d", m);
return 0;
}
```