Java求两个数的最大公约数及最小公倍数、求多个数的最大公约数及

火山日常啰嗦
今天参加腾讯笔试，做编程题时在最小公倍数、最大公约数这些这么简单的知识点上卡壳了，自信心受到强烈的打击，下来后猛复习了这方面的相关编程知识。

有以下几个关键点：
1、任意正整数的最大公约数、最小公倍数都是它本身。
2、求两个数的最大公约数（递归法、相减法、辗转相除法）
3、求两个数的最小公倍数，两个数的最小公倍数与它们的最大公约数之间存在如下关系：
某两个数a,b的最小公倍数=(a*b)/a与b的最大公约数
4、求多个数的最大公约数可以拆解成求两个数的最大公约数的过程
5、求多个数的最小公倍数可以拆解成求两个数的最小公倍数的过程

详细解析都在以下代码中：

public class Main {

//    递归法
    public  static int MaxCommonNum(int left , int right){
        /**
         * 我始终让left>right，这不是硬性要求哈，只是我个人的编程习惯
         */
        if(left<right){
            int temp = left;
            left = right;
            right = temp;
        }
        if((left%2!=0 || right%2!=0)&&(left%right!=0)) return 1;
        else if((left%2!=0 || right%2!=0)&&(left%right==0))  return right;
        else return 2*MaxCommonNum(left/2,right/2);
    }

//    相减法
    /**
     * @param left
     * @param right
     * @return
     * 1 若a>b,则a-=b
     * 2 若a<b,则b-=a
     * 3 若a==b,则a(或者b)就是所求的最大公约数
     * 4 若a!=b，则回去执行1、2步骤
     */
    public static int MaxCommonNum1(int left , int right){
        if(left==right) return left;
        if(left>right) left-=right;
        else right-=left;
        return MaxCommonNum1(left,right);
    }

//    辗转相除法
    /**
     * @param left
     * @param right
     * @return
     * 若要用left对right取模，那么要保证left>=right（反之亦然）
     * 1 若left%right==0,则right就是所求的最大公约数
     * 2 若left%right!=0,则将right的值赋给left，将left%riht的值赋给right，即left=right,right=left%right,然后再取模，判断余数是否为0
     * 3 重复这些步骤，直到left%right==0,则right就是所求的最大公约数
     *
     * */
    public static int MaxCommonNum2(int left , int right){
        if(left<right){
            int temp = left;
            left = right;
            right = temp;
        }
        if(left%right==0) return right;
        else return MaxCommonNum2(right,left%right);
    }

//    求多个数的最大公约数，借助求两个数的最大公约数的方法来求
    /**
     *
     * @param arr
     * @return
     * 求多个数的最大公约数，那么可以传入一个数组int arr[]
     * 1 取arr[0]赋给temp(某个正整数的最大公约数是它本身),然后通过求两个数的最大公约数的方法先求出temp与arr[1]的最大公约数，将结果赋给temp，则temp表示arr[0]与arr[1]的最大公约数
     * 2 然后再求temp与arr[2]的最大公约数，将结果赋给temp
     * 3 循环直到temp与剩余的每个数都求过最大公约数了，那么最后所求的那个就是这组数的最大公约数了
     *
     */
    public static int MaxCommonNumFromMultiNumbers(int arr[]){
        int temp = arr[0];
        for(int i=1;i<arr.length;i++){
            temp = MaxCommonNum(temp,arr[i]);
        }
        return temp;
    }

//    求两个数的最小公倍数

    /**
     *
     * @param left,right
     * 两个数a，b的最小公倍数=(a*b)/a与b的最大公约数
     *
     */
    public static int MinCommonNum(int left,int right){
        return left*right/MaxCommonNum(left,right);
    }

//    求多个数的最小公倍数

    /**
     *
     * @param arr
     * @return
     * 求多个数的最小公倍数跟求多个数的最大公约数的方法一样
     */
    public static int MinCommonNumFromNumbers(int arr[]){
        int temp = arr[0];
        for(int i=1;i<arr.length;i++){
            temp = MinCommonNum(temp,arr[i]);
        }
        return temp;
    }

    public static void main(String[] args) {

//        求两个数的最大公约数，有三种方法：
//        1、递归法
//        2、相减法
//        3、辗转相除法

//        求多个数的最大公约数，借助求两个数的最大公约数的方法来求

//        递归法
        System.out.println(MaxCommonNum(3,5));
        System.out.println(MaxCommonNum(12,8));

//        相减法
        System.out.println(MaxCommonNum1(3,5));
        System.out.println(MaxCommonNum1(12,8));

//        辗转相除法
        System.out.println(MaxCommonNum2(3,5));
        System.out.println(MaxCommonNum2(12,8));

//        求多个数的最大公约数
        int[] arr = {1,2,3,4,5,6};
        System.out.println(MaxCommonNumFromMultiNumbers(arr));

//        求两个数的最小公倍数
        System.out.println(MinCommonNum(3,5));
        System.out.println(MinCommonNum(12,8));

//        求多个数的最小公倍数
        int[] array = {4,5,6};
        int[] array1 = {1,2,3,4,5,6};
        System.out.println(MinCommonNumFromNumbers(array));
        System.out.println(MinCommonNumFromNumbers(array1));
   }
}

有误之处望请指出，望共同进步。感谢！