欧几里得算法与更相减损法复习

（1）欧几里得算法（辗转相除法），用于求两个整数的最大公因数

解释：

两个整数 a 和 b，假如a = b * x + y

a 和 b 的最大公因数是 d，

那么 a % d == 0，b % d == 0，也有 (b * x + y) % d == 0

∴ y % d == 0

即 a 和 b 的最大公因数也是 b 和 y 的最大公因数，而 y = a % b

1 int gcd (int a, int b) {
2     while (b != 0) {
3         int tmp = a;
4         a = b;
5         b = tmp % a;
6     }
7     return a;
8 }

或递归写法：

1 int gcd(int a, int b){
2     if (b == 0)
3         return a;
4     else
5         return gcd(b, a%b);
6 }

（2）更相减损法

假设 a > b

它们的最大公因数等于 a - b 和 b 的最大公因数

避免了大规模取模导致效率低下，但是运算次数比辗转相除法多很多

1 int gcd (int a, int b) {
2     if (a == b)
3         return a;
4     else if (a > b)
5         return gcd(a - b, b);
6     else if (a < b)
7         return gcd(b - a, a);
8 }