题目描述

输入两个正整数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 ;
}

参考结果

• 若有问题，请评论出来；