怎么用Java求最大公约数

这篇文章主要介绍"怎么用Java求最大公约数"，在日常操作中，相信很多人在怎么用Java求最大公约数问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答"怎么用Java求最大公约数"的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

/** * @date 2019/7/25 11:33 * description:求最大公约数 */public class CommonDivisor {    /**     * 第一版本     * 最简单的想法，找较小数的一半，从大到小，开始试着找出能够同时两个数整除最大数     * 这种方法暴力枚举，会循环很多次     *     * @param a     * @param b     * @return     */    public static int getGreatestCommonDivisor(int a, int b) {        int big = a > b ? a : b;        int small = a < b ? 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;    }    /**     * 第二版本     * 欧几里得算法：辗转相除法求最大公约数     * 两个正数a和b(a>b),它们的最大公约数等于a和b相除的余数c和b的最大公约数  我们可以使用递归的方法简化问题     * eg 10和25 的最大公约数等于 余数5和10的最大公约数 5     * 缺点 ： 两个数较大时 a%b的转换效率低     *     * @param a     * @param b     * @return     */    public static int getGreatestCommonDivisor2(int a, int b) {        int big = a > b ? a : b;        int small = a < b ? a : b;        if (big % small == 0) {            return small;        }        return getGreatestCommonDivisor2(big % small, small);    }    /**     * 第三版本     * 九章算术     * 更相减损术 :两个正整数a,b(a>b),他们的最大公约数等于a-b的差值c和较小数b的最大公约数     * 缺点：两数相差很大时，递归次数太大     *     * @param a     * @param b     * @return     */    public static int getGreatestCommonDivisor3(int a, int b) {        if (a == b) {            return a;        }        int big = a > b ? a : b;        int small = a < b ? a : b;        return getGreatestCommonDivisor3(big - small, small);    }    /**     * 第四版本     * 九章算术 更相减损术和辗转相除法结合起来， 更相减损术上使用位移操作     * 更相减损术 :两个正整数a,b(a>b),他们的最大公约数等于a-b的差值c和较小数b的最大公约数     * 缺点：两数相差很大时，递归次数太大     *     * @param a     * @param b     * @return     */    public static int getGreatestCommonDivisor4(int a, int b) {        if (a == b) {            return a;        }        if ((a & 1) == 0 && (b & 1) == 0) {            return getGreatestCommonDivisor4(a >> 1, b >> 1) << 1;        } else if ((a & 1) == 0 && (b & 1) != 0) {            return getGreatestCommonDivisor4(a >> 1, b);        } else if ((a & 1) != 0 && (b & 1) == 0) {            return getGreatestCommonDivisor4(a, b >> 1);        } else {            int big = a > b ? a : b;            int small = a < b ? a : b;            return getGreatestCommonDivisor4(big - small, small);        }    }    public static void main(String[] args) {        System.out.println(getGreatestCommonDivisor4(25, 5));        System.out.println(getGreatestCommonDivisor4(100, 80));        System.out.println(getGreatestCommonDivisor4(27, 14));    }}

到此，关于"怎么用Java求最大公约数"的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注网站，小编会继续努力为大家带来更多实用的文章！