Java求两个数的最大公约数

/**
 * 求两个数的最大公约数
 */
public class GreatestCommonDivisor {

    /**
     * 辗转相除法，也叫欧几里得算法
     * 定理：两个正整数a和b（a>b），它们的最大公约数等于a除以b的余数c和b之间的最大公约数
     * 缺点：当两个整数较大时，取模运算的效率会低
     * 时间复杂度接近O(log(max(a,b))),但取模算法性能较差
     *
     * @return
     */
    public static Integer getGreatestCommonDivisor(int a, int b) {
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor(big % small, small);
    }

    /**
     * 九章算法-更相减损数
     * 原理：两个正整数a和b（a>b）,它们最大公约数等于a-b的值c和较小值之间的最大公约数
     * 缺点：依靠两数求差的方式，当两数相差悬殊时，运算次数会很大
     * 性能不稳定：最坏时间复杂度为O(max(a,b))
     *
     * @param a
     * @param b
     * @return
     */
    public static Integer getGreatestCommonDivisorV2(int a, int b) {
        if (a == b) {
            return a;
        }
        int big = a > b ? a : b;
        int small = a < b ? a : b;
        return getGreatestCommonDivisorV2(big - small, small);
    }

    /**
     * 更相减和移位相结合算法：将辗转相除法和更相减算法结合起来，在更相减损数的基础上使用移位算法getGreatestCommonDivisor 简称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为偶数时 gcd(a,b) = gcd(a,b/2)=gcd(a,b>>1)
     * 当a和b均为奇数时，先利用更相减损术运算一次，gcd(a,b) = gcd(b,a-b),此时a-b必然时偶数，然后又可以使用移位运算
     * 特点：避免了取模运算，而且算法稳定，时间复杂度为O(log(max(a,b)))
     *
     * @param a
     * @param b
     * @return
     */
    public static Integer getGreatestCommonDivisorV3(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {
            return getGreatestCommonDivisorV3(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) != 0) {
            return getGreatestCommonDivisorV3(a >> 1, b);
        } else if ((a & 1) != 0 && (b & 1) == 0) {
            return getGreatestCommonDivisorV3(a, b >> 1);
        } else {
            int big = a > b ? a : b;
            int small = a < b ? a : b;
            return getGreatestCommonDivisorV3(big - small, small);
        }
    }

    public static void main(String[] args) {
        System.out.println(getGreatestCommonDivisor(25, 5));
        System.out.println(getGreatestCommonDivisor(14, 28));

        System.out.println(getGreatestCommonDivisorV2(25, 5));
        System.out.println(getGreatestCommonDivisorV2(14, 28));

        System.out.println(getGreatestCommonDivisorV3(25, 5));
        System.out.println(getGreatestCommonDivisorV3(14, 28));
    }
}