欧几里德算法

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：

定理：gcd(a,b) = gcd(b,a mod b)

证明：a可以表示成a = kb + r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a, d|b，而r = a – kb，因此d|r
因此d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数，则
d | b , d |r ，但是a = kb +r
因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证

最小公倍数等于两个数的乘积除以最大公约数

/*
7-26 最大公约数和最小公倍数（15 分）

本题要求两个给定正整数的最大公约数和最小公倍数。
输入格式:

输入在一行中给出两个正整数M和N（≤1000）。
输出格式:

在一行中顺序输出M和N的最大公约数和最小公倍数，两数字间以1空格分隔。
输入样例:

511 292

输出样例:

73 2044

*/
#include <stdio.h>

int gcd(int, int);
int rec_gcd(int, int);
int lcm(int, int);
int main(void)
{
        int m, n;
        int g, l;
        scanf("%d%d", &m, &n);
        g = gcd(m, n);
        l = lcm(m, n);

        printf("%d %d\n", g, l);

        return 0;
}

int gcd(int u, int v)
{
        int r;
        while (v) {
                r = u % v;
                u = v;
                v = r;
        }

        return u;
}

int rec_gcd(int u, int v)
{
        if (!v)
                return u;
        else
                return rec_gcd(v, u % v);
}

int lcm(int u, int v)
{
        int r = gcd(u, v);
//      int l = u * (v / r);
//      int l = v * (u / r);
        int l = u * v / r;

        return l;
}

运行结果：

[lhf@lhf programming]$ ./26
511 292
73 2044