最大公约数 —— 小灰的算法之旅读书笔记

辗转相除法（欧几里得算法）

两个正整数a和b（a>b)，他们的最大公约数等于a除以b的余数c和b之间的最大公约数

更相减损术

两个整数a和b（a>b），它们的最大公约数等于a-b的差值c和b的最大公约数

更相减损术和移位结合

• a和b都为偶数的时候，a和b的最大公约数为2*(a/2和b/2的最大公约数)

• a和b为一奇一偶的时候，将偶数除以2，求两个奇数的最大公约数

• a和b为奇数的时候，使用更相减损术运算一次，继续求最大公约数

代码实现

public class GreatestCommonDivisor {
    public int gcd(int a, int b) {
        //如果a==b,即为a和b的最大公约数
        if (a == b) {
            return a;
        }
        //如果a和b都是偶数
        if ((a&1) == 0 && (b&1) == 0) {
            return gcd(a>>1, b>>1)<<1;
        } else if ((a&1) == 0 && (b&1) != 0) { //a是偶数,b是奇数
            return gcd(a>>1, b);
        } else if ((a&1) != 0 && (b&1) == 0) { //a是奇数,b是偶数
            return gcd(a, b>>1);
        } else { //a和b都是奇数,使用更相减损术
            int big = a > b ? a : b;
            int small = a > b ? b : a;
            return gcd(big - small, small);
        }
    }

    public static void main(String[] args) {
        GreatestCommonDivisor greatestCommonDivisor = new GreatestCommonDivisor();
        System.out.println(greatestCommonDivisor.gcd(25, 5));
        System.out.println(greatestCommonDivisor.gcd(100, 80));
        System.out.println(greatestCommonDivisor.gcd(27, 14));
    }
}