关于算法:求最小公倍数

题目

如果两个数很大，怎么求最大公约数，最小公倍数？
如果是n个数呢？比方1000个数的最小公倍数

输出
2 4 6
3 2 5 7

输入
12
70

思路

首先最大公约数能够用辗转相除法，定义为lcm(m,n)，而后再定义一个办法gcd(m,n)求最大公约数，用公式法 ：最小公倍数 = m * n / lcm(m,n),应用一个数组nums来装输出的数据，大小n由输出决定int nums[] = new int[n];,而后在应用一个while循环，来输出装进数组nums的数据。最初定义一个int a，贮存gcd(m,n)参数中的m。

不晓得辗转相除法，能够看我的这篇博客，具体介绍了的，很简略。

代码

public class Test4 {
    public static void main(String[] args) {
        int i = 0,m;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//输出要输的个数
        int nums[] = new int[n];
        while (n != 0 ){
            m = sc.nextInt();
            if (m == 0){

            }else{
                nums[i] = m;
                i++;
            }
            n--;
        }
        int a =nums[0];//lcm的第一个参数
//        System.out.println(Arrays.toString(nums));
        for (int j = 1 ; j < nums.length; j++){
            a =  gcd(a,nums[j]);
        }
        System.out.println("他们的最小公倍数="+a);
    }
    //求最大公因数
    public static int lcm(int m,int n ){
        int left = (m > n)? m : n; //右边是较大的数
        int right = (m > n)? n : m; //左边是较小的数
        if ((left % right) == 0){
            return  right;
        }
        return lcm(right , left % right);
    }
    //求最小公倍数
    public static int gcd(int m,int n){
        return m * n /lcm(m , n);
    }

}