问题：

求出两个正整数的最大公约数

解法1：

暴力枚举法，从较小数的一半开始，找到一个合适的整数

1    function getGreatestCommonDivisorV1(a:number, b:number):number {
2        let big = a > b ? a :b;
3        let small = a > b ? b :a;
4        if(big % small === 0) {
5            return small
6        }
7        for (let i = Math.floor(small/2); i > 1; i--) {
8            if(small % i ===0 && big % i === 0) {
9                return i
10            }
11        }
12        return 1
13    }
14

解法2：

辗转相除法，又名欧几里得算法

该算法基于一条定律：两个正整数 a 和 b (a > b)，它们的最大公约数等于 a 除以 b 的余数 和 b 的最大公约数

1    function getGreatestCommonDivisorV2(a:number, b:number):number {
2        let big = a > b ? a : b;
3        let small = a > b ? b : a;
4        if(big%small === 0) {
5            return small
6        }
7        return getGreatestCommonDivisorV2(big%small, small)
8    }
9

该算法存在问题：大数取模运算性能较差

解法3：

更相减损术，出自《九章算术》

原理：两个正整数 a 和 b (a > b)，它们的最大公约数等于 a 减 b 的差值 和 b的最大公约数

1    function getGreatestCommonDivisorV3(a:number, b:number):number {
2        if(a === b) {
3            return a
4        }
5        let big = a > b ? a : b;
6        let small = a > b ? b :a;
7    
8    
9        return getGreatestCommonDivisorV3(big - small, small)
10    }
11

该算法存在问题：递归次数较多

解法4：

此解法基于几个巧妙地方法：

判断一个正整数 a 是否为偶数 a%2 === 0 可以转换为 位运算 (a & 1) === 0

对 正整数 a， a/2 转换为位运算 a >> 1

a*2 转换为位运算 a << 1

求两个正整数的最大公约数 24、60

基于质因数分解法

24 = 2 * 2 * 2 *3

64 = 2 * 2 * 3 * 5

公有质因数为 2 * 2 * 3，则最大公约数为 2 * 2 * 3 = 12

由以上可以得出

设求最大公约数函数 f

当 a, b 都为偶数时 f(a, b) = 2 * f(a, b)

当 a 为偶数，b 为奇数时 f(a, b) = f(a/2, b)

设求最大公约数的方法为 gcd,

当 a，b 都为偶数时， gcd(a, b) = 2 * gcd(a/2, b/2) = 2 * gcd(a >> 1, b >>1)

当 a为偶数，b为奇数时，gcd(a, b) = gcd(a/2, b) = gcd(a >> 1, b)

当 a 为 奇数，b为偶数时，同上转换为 b >> 1

当 a，b 都为 奇数时，使用更相减损法，gcd(a, b) = gcd(a-b, b) 假设 a > b，此时 两奇数相减结果必定为 偶数

1    function getGreatestCommonDivisorV4(a:number, b:number):number{
2        if(a === b){
3            return a
4        }
5        let big = a > b ? a : b;
6        let small = a > b ? b : a;
7        let isBigEven = (big & 1 )=== 0;
8        let isSmallEven = (small & 1) === 0;
9        // 两个数都为偶数
10        if(isBigEven && isSmallEven) {
11            return getGreatestCommonDivisorV4(big >> 1, small >>> 1) << 1
12        } else if(isBigEven) {
13        // 两个数一个为偶数 一个为奇数
14            return getGreatestCommonDivisorV4(big >> 1, small)
15        } else if(isSmallEven) {
16            return getGreatestCommonDivisorV4(big, small >> 1)
17        } else {
18            // 两个数都为奇数
19            return getGreatestCommonDivisorV4(big - small, small)
20        }
21    }
22

摘要总结自: 漫画算法 小灰的算法之旅