Java求最大公约数(6种解法总结)

时间：2025-03-25 11:37:18

目录

主函数

1.暴力枚举法

2.辗转相除法

3.辗转相除法 ---递归调用

4.辗转相除法 ---递归调用---简化写法

5.调用函数递归 更相减损法

6.调用函数递归 更相减损法--简化

主函数

 public static void main(String[] args) {
        Scanner sc = new Scanner();
        int a = ();
        int b = ();
        int gcd = gcd(a, b);
        (gcd);

    }

1.暴力枚举法

    public static int gcd(int a, int b) {
        int min = a < b ? a : b;//判断并取出两个数中小的数
        for (int i = min; i >= 1; i--) { //循环,从最小值开始,依次递减,直到i=1
            if (a%i==0&&b%i==0){    //当i能同时被A和B余尽时,返回i
                return i;
            }
        }
        return 0;
    }

}

2.辗转相除法

 public static int gcd(int a, int b) {// 辗转相除法
        int c = a % b;   //先将a对b取余
        while (c != 0) {   //当余数不等于0时,一直进行循环,直到余数等于0,公约数就为b
            a = b;         //将a对b的余数再对b取余,直到循环结束
            b = c;
            c = a % b;
        }
        return b;
    }

3.辗转相除法 ---递归调用

    public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归
        int max = a > b ? a : b; //求出大的数
        int min = a < b ? a : b; //求出小的数
        if(max%min==0){
            return min;      //当大数模小数能余尽时,最大公约数就是小的数
        }
        return gcd(max%min,min);//递归函数,参数去前两个数的余数,和小的数

4.辗转相除法 ---递归调用---简化写法

public static int gcd(int a, int b) {// 辗转相除法 改进,调用函数递归
        return (a % b == 0) ? b : gcd(b, a%b );// 相同思路,三元运算/简化写法
    }

1.如果a余b等于0，说明b就是最大公约数

2.否则，进行递归，b代替曾经的a，让a%b产生的余数代替曾经的b。

3.始终确保大数%小数

4.即使b位置上是值大于a, b代替a后，a（小数）%b(大数) = a ，相当于替换位置

5. （b,a%b）的位置不能交换，否则无法跳出递归

5.调用函数递归 更相减损法

 public static int gcd(int a, int b) {//调用函数递归 更相减损法
        int max = a>b?a:b;
        int min = a<b?a:b;
        if(max%min==0){
            return min;
        }
        return gcd(max-min,min);//相同思路,将%改为-,优化速度
    }

6.调用函数递归 更相减损法--简化

    public static int gcd(int a, int b) {//调用函数递归 更相减损法 简易写法
        if (a < b) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        return (a % b == 0) ? b : gcd(a - b, b);
    }

简化不用找大小数，把大数放到前面

因为小数减大数为负数，所以要把大数替换到前面，

    public static int gcd5(int a, int b) {//调用函数递归 更相减损法 简易写法
        return (a % b == 0) ? b : a > b ? gcd5(a - b, b) : gcd5(b-a,a);
    }

压行写法，就是三目嵌套，就是可读性不高

相关文章