[编程入门]最大公约数与最小公倍数(递归)-题解（Java代码）

解题思路: 先用更相减损法求出最大公约数(递归)，在用公式求最小公倍数

注意事项: 母鸡

参考代码:

/*
     * 输入两个正整数m和n，求其最大公约数和最小公倍数。
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int arr[] = {sc.nextInt(),sc.nextInt()};
        int divisor = commonDivisor(arr[0],arr[1]);
        System.out.print(divisor+" ");
        System.out.print((arr[0]*arr[1])/divisor);//公式：两个数的积=最大公约数*最小公倍数
    }
    
    //最大公约数:更相减损法
        /*
         * 第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
           第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
         */
    public static int commonDivisor(int a,int b) {
        int difference = 0;//记录 最大值-最小值 的结果
        
        //判断确定 最大值 和 最小值  判断好了才能开始递归
        if (a>b) {
            difference = subtraction(a,b);
            return difference==b?difference:difference;
        }else {
            difference = subtraction(b,a);
            return difference==a?difference:difference;
        }
    }
    
    public static int subtraction(int max,int min) {
        int difference = max-min;//最大最小值的差
        if (min==difference) {//差于最小值相等 做为出口
            return difference;
        }
        return commonDivisor(min,difference);//开始递归(因为不能确定差就一定大于或者小于min才把结果放回去再做一次判断)
    }