最大公约数

最大公约数

公约数指能同时被整数 A 和 B 整除的数,最大公约数是指约数中最大的一个。

先按照定义来进行计算,找一个能同时被整数 A、B 整除的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
* 计算两个整数 a, b 的最大公约数
*
* @param a
* @param b
*/
const getGreastCommonDivisor = (a, b) => {
if (!(Number.isInteger(a) && Number.isInteger(b))) {
throw new Error('Invalid arguments');
}

const flag = a >= b,
big = flag ? a : b,
small = flag ? b : a;

if (big % small === 0) return small;

for (let i = Number.parseInt(small / 2); i > 1; i--) {
if ((small % i === 0) && (big % i === 0)) {
return i;
}
}

return 1;
}

这种方式简单暴力,直接从较小整数的一半开始查找,但效率明显不高,特别是碰到大整数时,需要查找成千上万次,时间复杂度为 O(min(a, b))

为了提高效率,下面介绍两种更高效的计算算法:

欧几里得算法

欧几里得算法(Euclidean algorithm),在数学中也叫辗转相除法。该算法的原理为:两个自然数 A、B(A>B),它们的最大公约数等于 A 除以 B 的余数 C 和 B 之间的最大公约数

了解了原理之后,我们可以借助递归的思想来简化整个求解过程,将求 A 和 B 之间的最大公约数转变为求 A 除以 B 的余数 C 和 B 之间的最大公约数,然后再将求 C 和 B 之间的最大公约数转换为求 B 除以 C 的余数 D 和 B 之间的最大公约数,以此类推,直到两个数能够整除或其中一个数为 1 为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 计算两个整数 a, b 的最大公约数
*
* @param a
* @param b
*/
const getGreastCommonDivisor = (a, b) => {
if (!(Number.isInteger(a) && Number.isInteger(b))) {
throw new Error('Invalid arguments');
}

const flag = a >= b,
big = flag ? a : b,
small = flag ? b : a;

if (big % small === 0) return small;

return getGreastCommonDivisor(big % small, small);
}

更相减损术

更相减损术是《九章算术》中的一种求最大公约数的算法:

可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也。以等数约之。

翻译过来就是:两个自然数 A、B(A>B),它们的最大公约数等于 A 减 B 的差值 C 和 B 之间的最大公约数

借助递归的思想,过程和欧几里得算法类似,将两个大整数之间的运算逐渐简化为两个小整数的运算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
* 计算两个整数 a, b 的最大公约数
*
* @param a
* @param b
*/
const getGreastCommonDivisor = (a, b) => {
if (!(Number.isInteger(a) && Number.isInteger(b))) {
throw new Error('Invalid arguments');
}

const flag = a >= b,
big = flag ? a : b,
small = flag ? b : a;

if (big % small === 0) return small;

return getGreastCommonDivisor(big - small, small);
}

相比欧几里得算法,更相减损术的运算次数要多很多; A、B 的差值越大,计算次数越多。