题目描述
输入两个正整数m和n，求其最大公约数和最小公倍数。
输入
两个整数
3输出
最大公约数，最小公倍数
样例输入
5 7
样例输出
1 35
解析
辗转相除法
辗转相除法是古希腊求两个正整数的最大公约数的，也叫欧几里德算法，其方法是用较大的数除以较小的数，上面较小的除数和得出的余数构成新的一对数，继续做上面的除法，直到出现能够整除的两个数，其中较小的数（即除数）就是最大公约数。以求288和123的最大公约数为例，操作如下：
288÷123=2余42
123÷42=2余39
42÷39=1余3
39÷3=13
所以3就是288和123的最大公约数。
注意事项:
辗转相除法在编程的实现，一个弊端就是必须是用大数对小数取余，所以要提前用条件语句判断三种可能情况
因为变量数较多，或者会有重复使用先前变量的步骤，而先前变量可能被改变，所以要提前用一些中间变量储存先前变量的值。
两数的乘积再除以两数的最大公约数法。
这个方法虽然比较复杂，但是使用范围很广。因为两个数的乘积等于这两个数的最大公约数和最小公倍数的乘积。例如: 4和6的最大公约数是2，最小公倍数是12，那么，4X6=2X 12。
运行结果
#include<iostream>
using namespace std ;
int main()
{
int t = 1 ;//取余计算的余数，赋值为1是为了方便进入while循环
int m,n ;
cin>>m>>n ;
int nNum1 = m ;//中间变量：保存m
int nNum2 = n ;//中间变量：保存n
if(m > n)//判断两数的大小，保证用大数对小数取余
{
while(t != 0)
{
t = m % n ;
m = n ;//将随后循环中的m变成本次循环计算后的n
n = t ;//将随后循环中的n变成本次循环计算后的t
}
int b = (nNum1 * nNum2) / m ;//利用性质求出最小公倍数
cout<<m<<" "<<b<<endl ;
}
else if(m < n)
{
while(t != 0)
{
t = n % m ;
n = m ;
m = t ;
}
int b = (nNum1 * nNum2) / n ;
cout<<n<<" "<<b<<endl ;
}
else//当m=n时，最大公因数和最小公倍数相等，都等于他们本身
{
cout<<n<<" "<<n<<endl ;
}
return 0 ;
}
参考结果
- 若有问题，请评论出来；
