题目 1027: [编程入门]自定义函数处理最大公约数与最小公倍数

写两个函数，分别求两个整数的最大公约数和最小公倍数，用主函数调用这两个函数，并输出结果两个整数由键盘输入。

两个数

最大公约数 最小公倍数

6 15

3 30

解题思路:

欧几里得算法又称辗转相除法，用来求两个正整数的最大公约数。以上面的1997和615为例，用欧几里得算法求解如下：

1997 = 615 * 3 + 152

615 = 152 * 4 + 7

152 = 7 * 21 + 5

7 = 5 * 1 + 2

5 = 2 * 2 + 1

2 = 2 * 1 + 0

当被加的数为0时，可以得出，1997和615的最大公约数为1。

以上做法的依据是以下定理：

两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。

用数学表示为： gcd(a, b) = gcd(b, a mod b) 

 

最小公倍数就在算出最大公因数之后就跟简单了：gcd(a, b) * lcm(a, b) = a * b;

#include<stdio.h>
int gcd(int i, int j);
int LCM(int m, int n);
 
int main(void)
{
    int M, N, lcm = 1;
    while (scanf("%d %d", &M, &N) != EOF)
    {
        printf("%d ", gcd(M, N));
        printf("%d", LCM(M, N));
    }
    return 0;
}
 
int gcd(int i, int j)
{
    int mo;
    while (j > 0)
    {
        mo = i % j;
        i = j;
        j = mo;
    }
    return i;
}
 
int LCM(int m, int n)
{
    int lcm;
    lcm = m * n / gcd(m, n);
    return lcm;
}