Java求最大公约数

问题：写一段代码，求两个整数的最大公约数，尽量优化代码
最大公约数，同时可以被a和b整除
辗转相除法：俩个正整数a,b,他们的最大公约数等于a/b的余数c和b的最大公约数。
**更相减损术：**俩个正整数a,b，他们的最大公约数等于a-b的差值c和较小数b的最大公约数。
具体代码实现如下：

 /**
     * 求最大公约数
     */
    @Test
    public void test3() {
        System.out.println(getGreatestCommonDivisor(25, 5));
        System.out.println(getGreatestCommonDivisor2(25, 5));
        System.out.println(getGreatestCommonDivisor3(25, 5));
    }

    /**
     * 求最大公约数
     *
     * @param a a
     * @param b b
     * @return 最大公约数
     */
    public static int getGreatestCommonDivisor(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        if (big % small == 0) {
            return small;
        }
        for (int i = small / 2; i > 1; i--) {
            if (small % i == 0 && big % i == 0) {
                return i;
            }
        }
        return 1;
    }

    /**
     * 求最大公约数 辗转相除法
     *
     * @param a a
     * @param b b
     * @return 最大公约数
     */
    public static int getGreatestCommonDivisor2(int a, int b) {
        int big = Math.max(a, b);
        int small = Math.min(a, b);
        if (big % small == 0) {
            return small;
        }
        return getGreatestCommonDivisor2(big % small, small);
    }

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

我们都知道，移位运算的性能非常好，我们可以在更相减损术的基础上使用移位运算。

    /**
     * 求最大公约数 更相减损术
     *
     * @param a a
     * @param b b
     * @return 最大公约数
     */
    public static int gcd(int a, int b) {
        if (a == b) {
            return a;
        }
        // 偶数，偶数
        if ((a & 1) == 0 && (b & 1) == 0) {
            return gcd(a >> 1, b >> 1) << 1;
        } //偶数，奇数
        else if ((a & 1) == 0 && (b & 1) != 0) {
            return gcd(a >> 1, b);
        } // 奇数 ，偶数
        else if ((a & 1) != 0 && (b & 1) == 0) {
            return gcd(a, b >> 1);
        } else {
            int big = Math.max(a, b);
            int small = Math.min(a, b);
            return gcd(big - small, small);
        }

    }

最后

以上就是单薄机器猫为你收集整理的Java求最大公约数的全部内容，希望文章能够帮你解决Java求最大公约数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。