【算法】辗转相除法求最大公约数

辗转相除法，又index.php/tags-41973.html" >���欧几里德算法（Euclidean Algorithm），是求两个数的最大公约数（greatest common pisor）的一种方法。用较大的数除以较小的数，再以除数和余数反复做除法运算，当余数为0时，取当前算式除数为最大公约数。

（）

求30和18的最大公约数：

30 / 18 = 1 余 12

（）

18 / 12 = 1 余 6

12 /   6 = 2 余 0

所以，30和18的最大公约数为6。

如果用小数除以大数，只是过程多了一步，结果没有差别，所以写代码时不用考虑两个数的大小。

18 / 30 = 0 余 18

30 / 18 = 1 余 12

18 / 12 = 1 余 6

12 /   6 = 2 余 0

辗转相除法的原理：

a / b = q 余 r，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除。或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数。即被除数与除数的最大公约数，就是除数与余数的最大公约数。

#include int main(){int m = 0;int n = 0;scanf("%d %d", &m, &n);int r = 0;while (r = m % n){m = n; // 以除数作为被除数n = r; // 以余数作为除数}printf("%d\n", n); // 最后的除数为最大公约数return 0;}

由于被除数与除数的最大公约数，就是除数与余数的最大公约数，即gcd(a, b) = gcd(b, a%b)，所以也可以设计一个递归算法计算最大公约数。

#include int gcd(int a, int b){if (b == 0)return a;elsereturn gcd(b, a % b);}int main(){int m = 0;int n = 0;scanf("%d %d", &m, &n);printf("%d\n", gcd(m, n));return 0;}

最小公倍数是根据最大公约数求得的，最小公倍数 = 两数乘积 / 最大公约数。