标签归档:最小公倍数

最大公约数和最小公倍数

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数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