最大公约数与最小公倍数

解题思路:

最大公约数的求法

欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。扩展欧几里得算法可用于RSA加密等领域。假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：
1997 ÷ 615 = 3 (余 152)
615 ÷ 152 = 4(余7)
152 ÷ 7 = 21(余5)
7 ÷ 5 = 1 (余2)
5 ÷ 2 = 2 (余1)
2 ÷ 1 = 2 (余0)
至此，最大公约数为1以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

最小公倍数的求法

比如6和8共同的公约数就是2。2乘3和2乘4分别是它们的约数，找公共的约数2。最小公倍数是2乘3乘4=24。2是最大公约数。3和4分别是各自的另一个约数，把它们都乘在一起。即：最小公倍数=a*b/最大公约数

注意事项:

参考代码:

#include<iostream>

using namespace std;

int m, n;

int gongyue(int m, int n)

{

if (n == 0)

return m;

else

return gongyue(n, m % n);

}

int gongbei(int m, int n)

{

return (m * n / gongyue(m, n));

}

int main()

{

cin >>m>> n;

cout << gongyue(m, n)<<endl;

cout << gongbei(m, n)<<endl;