c++输入两个正整数m和n,求其最大公约数和最小公倍数
时间: 2023-05-31 15:21:02 浏览: 1002
### 回答1:
输入两个正整数m和n,求其最大公约数和最小公倍数的C++代码如下:
```c++
#include <iostream>
using namespace std;
int gcd(int a, int b) { // 求最大公约数
if (b == 0) return a;
return gcd(b, a % b);
}
int lcm(int a, int b) { // 求最小公倍数
return a * b / gcd(a, b);
}
int main() {
int m, n;
cin >> m >> n;
cout << "最大公约数:" << gcd(m, n) << endl;
cout << "最小公倍数:" << lcm(m, n) << endl;
return 0;
}
```
其中,`gcd`函数用于求最大公约数,采用递归的方式实现;`lcm`函数用于求最小公倍数,直接利用最大公约数求解。在主函数中,先输入两个正整数m和n,然后调用`gcd`和`lcm`函数分别求解最大公约数和最小公倍数,并输出结果。
### 回答2:
先解释一下什么是最大公约数和最小公倍数。
最大公约数,简称gcd(greatest common divisor),又称最大公因数、最大公因子。指能够同时整除两个或多个整数的最大正整数。例如,6和15的最大公约数是3。
最小公倍数,简称lcm(least common multiple),又称最小公倍数,是指能够被同时整除两个或多个整数的最小正整数。例如,6和15的最小公倍数是30。
以下是求最大公约数和最小公倍数的方法:
方法一:枚举法
最大公约数的求解方法比较简单,可以通过枚举的方式来求解。从较小的那个数开始,依次递减,找到两个数都能整除的最大的数即为它们的最大公约数。这个方法虽然简单,但对于大数的计算会非常耗时。
最小公倍数的求解方法也可以使用枚举的方式,从两个数中较大的那个数开始,不断增加,直到找到两个数都能整除的最小的数即为它们的最小公倍数。同样的,这个方法也不适用于大数的计算。
方法二:辗转相除法
辗转相除法是求最大公约数的一种更为高效的方法。具体步骤如下:
假设两个数为m和n,其中m>n。
1.用m除以n,得到余数r1。
2.如果r1=0,则n就是最大公约数。
3.如果r1≠0,则用n除以r1,得到余数r2。
4.如果r2=0,则r1就是最大公约数。
5.如果r2≠0,则继续用r1除以r2,得到余数r3……如此循环,直到得到余数为0为止,此时所得到的除数就是最大公约数。
最小公倍数的求解可以利用最大公约数。最小公倍数等于两个数之积除以它们的最大公约数。即lcm(m,n)=(m*n)/gcd(m,n)。
示例:
假设要求6和15的最大公约数和最小公倍数。
使用辗转相除法来计算它们的最大公约数:
1. 用15除以6,得到余数3。
2. 用6除以3,得到余数0。
3. 所以最大公约数为3。
使用最小公倍数公式来计算它们的最小公倍数:
lcm(6,15)=(6*15)/3=30。
因此,6和15的最大公约数为3,最小公倍数为30。
### 回答3:
最大公约数,简称“最大公因数”,英文缩写为GCD(Greatest Common Divisor),是指两个或多个整数共有约数中,最大的那个数。求最大公约数有多种方法,包括辗转相除法、更相减损法等。其中,辗转相除法是最常用的方法。其步骤如下:
1. 比较m和n的大小,将较小的数赋值给temp。
2. 用较大的数除以temp,如果余数是0,则temp就是最大公约数;
3. 如果余数不是0,则将temp赋值给较小数,用余数再去除temp,重复2步骤,直到余数为0为止。
最小公倍数,简称“最小公倍数”,英文缩写为LCM(Least Common Multiple),是指两个或多个整数公有的倍数中,最少的那个数。可以通过求出两个数的最大公约数来求得最小公倍数,公式为(a*b)/gcd(a,b)。
综上所述,要求出两个正整数m和n的最大公约数,我们可以使用辗转相除法,而要求最小公倍数,则可以使用最大公约数公式求解。
阅读全文