本文共 2413 字，大约阅读时间需要 8 分钟。

/** * 求两个数的最大公约数 */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));    }}

转载地址：http://pqsvi.baihongyu.com/