更相减损术

更相减损术 出自中国古代 '九章算术', 是一种最大公约数的算法.

他的原理简单: 两个正整数a和b(a>b), 他们的最大公约数等于a-b的差值c和较小数b之间的最大公约数.

    /**
     * 更相减损术
     *
     * @return 最大公约数
     */
    public static int getGreatestCommonDivisorV1(int a, int b) {
        if (a == b) {
            return a;
        }
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        return getGreatestCommonDivisorV1(big - small, small);
    }

辗转相除法

辗转相除法, 又名欧几里得算法, 该算法目的是求出两个正整数的最大公约数.

该算法基于一个定理: 两个正整数a和b(a>b), 他们的最大公约数等于a除以b的余数c和b之间的最大公约数.

    /**
     * 辗转相除法 (欧几里得算法)
     *
     * @return 最大公约数
     */
    public static int getGreatestCommonDivisorV2(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisorV2(big % small, small);
    }