如何求两个数字的最大公约数,本文主要是讲解和证明 Euclid、更相减损法和 Stein 两种方法。

欧几里德算法

欧几里德算法又称作是辗转相除法。主要是用来求 a 和 b 两个数字的最大公约数。

假设 a 可以表示成 bq + r 的形式。

  • 如果 r 等于 0,那么 b 就是 a 和 b 的最大公约数。
  • 如果 r 不等于 0,那么 a 和 b 的任意一个公约数都是 r 的公约数。因为 r 等于 a - bq,那么假设有一个公约数叫做 d,其中 a 等于 sd,b 等于 td,那么 r 等于 (s-tb)q。此点对于所有公约数都成立,那么 a 和 b 的最大公约数就是 b 和 r 的最大公约数了。

用 C++ 实现上面的思路。

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

更相减损法

上面的算法中 a % b 操作的性能比较低,可以使用「更相减损法」。假设 a 大于 b,那么 a 和 b 的最大公约数等于 a - b 和 b 的最大公约数。

用 C++ 实现该算法。

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

Stein

上面两种方法遇到大整数都会有问题,要么是取余操作慢,要么是递归很深。Stein 算法由 J. Stein 于 1961 年提出,它只有整数的移位和加减法。 在了解 Stein 算法之前,先要明白下面两个等式:

如果 k 等于 2,那么说明最大公约数肯定能被 2 整除。

知道上面的规律后,看下该算法:

  • 如果 a 等于 0,那么返回 b;
  • 如果 b 等于 0,那么返回 a;
  • 如果 a 和 b 都是偶数,那么提取出 2 来,只需要都移位即可。
  • 如果 a 是偶数,b 是奇数,对 a 进行移位,因为最大公约数肯定不能被 2 整除。
  • 如果 b 是偶数,a 是奇数,对 b 进行移位,因为最大公约数肯定不能被 2 整除。
  • 如果 a 和 b 都是奇数,把 a 和 b 的差与 a 和 b 之间的较小的数求最大公约数。

用 C++ 实现上面的思路。

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

该算法不仅避免了取模运算,而且性能稳定,时间复杂度是