【Java编程】输出两个数或N个数的最大公约数

输入两个或多个正整数，输出它们的最大公约数，例：

• 输入：25 10 15
• 输出：5

首先，需要明确什么叫最大公约数，即几个数中公有的最大的因数。
其次，怎么求解最大因数呢？一个数，我们可以求出所有的质因子，那多个数呢？显然也能。
最后，通过下面的图解（待画…）分析得知，最大公约数＝所有公有的质因子的乘积。

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String[] str = sc.nextLine().split(" ");
            int number1 = Integer.parseInt(str[0]);
            int number2 = Integer.parseInt(str[1]);

            List list = new ArrayList<>();
            Main.getFactor(list, number1, number2);

            System.out.print(number1 + "与" + number2 + "的公有质因子为：");
            list.forEach(integer -> System.out.print(integer + " "));
            System.out.println();
            int result = 1;
            for (Integer integer : list) {
                result = result * integer;
            }
            System.out.println("最大公因子为：" + result);
        }
    }

    private static void getFactor(List list, int number1, int number2) {
        int number = Math.min(number1, number2);
        for (int i = 2; i <= number; i++) {
            if (number1 % i == 0 && number2 % i == 0) {
                list.add(i);
                Main.getFactor(list, number1 / i, number2 / i);
                return;
            }
        }
    }
}

• 两个互质的整数为什么没有求出公有质因子1呢？

可以看到，已经初步实现两个数的最大公因数的求解，但是当输入的两个互质的整数时，在list中并没有存放最大公因数1，我认为1只能算是最大公因数，但是并不算公有的质因子，因为质因数需要大于等于2，如果这里加入list.add(1)也是可以的，看自己的理解。

private static void getFactor(List list, int number1, int number2) {
    int number = Math.min(number1, number2);
    for (int i = 2; i <= number; i++) {
        if (number1 % i == 0 && number2 % i == 0) {
            list.add(i);
            Main.getFactor(list, number1 / i, number2 / i);
            return;
        }
    }
    list.add(1);
}

• 当输入的为两个以上的正整数时，如何得出最小的那个数？

当输入数为两个整数时，可以通过int min = Math.min(number1, number2)获取，但是当数为多个的时候呢？我们可以利用List的有序性，如果进入递归的List本身就是有序的，那么int min = list.get(0)就是最小的数。

// 这里使用Java8的流快速的对输入的字符串数组进行类型转换和排序处理
String[] str = sc.nextLine().split(" ");
List inputNumbers = Stream.of(str).map(Integer::parseInt).sorted().collect(Collectors.toList());

// 排序后，在递归里面首个元素就是最小元素
int min = inputNumbers.get(0);

求两个或多个正整数的最大公约数，

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextLine()) {
            String[] str = sc.nextLine().split(" ");
            List inputNumbers = Stream.of(str).map(Integer::parseInt).sorted().collect(Collectors.toList());
            List list = new ArrayList<>();
            getFactor(list, inputNumbers);
            int result = 1;
            for (Integer integer : list) {
                result = result * integer;
            }
            System.out.println(result);
        }
    }

    private void getFactor(List list, List inputNumbers) {
        int min = inputNumbers.get(0);
        for (int i = 2; i <= min; i++) {
            boolean flag = true;
            for (Integer inputNumber : inputNumbers) {
                flag = flag && inputNumber % i == 0;
            }
            if (flag) {
                list.add(i);
                // 这是流的特性，直接用i会报编译错误。
                int finalI = i;
                List newInputNumbers = inputNumbers.stream().map(integer -> integer / finalI).collect(Collectors.toList());
                getFactor(list, newInputNumbers);
                return;
            }
        }
        list.add(1);
    }
}

上述代码输出结果如下，已经满足题目要求（可以去掉公有质因子的输出）。

上述思路方案仅供参考，欢迎补充更多更好的方案！