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