关于算法:求最小公倍数

题目

如果两个数很大，怎么求最大公约数，最小公倍数？
如果是 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);
    }

}