Java编程题 - 输出一个整数的所有质因子并排列

输入一个正整数n，输出该整数的所有质因子，并按从小到大顺序排列！，例：

• 输入：40
• 输出：40=2*2*2*5

首先，观察这种输出结果40=2*2*2*5，很容易想到就是 “短除法”，虽然你可能忘了什么叫短除法，但是你肯定知道怎么计算，也就是从最小质数2开始相除，一直除到结果为质数为止，比如40刚好能被2整除，2是一个质数，那么2就是40的一个质因子。
其次，40/2=20，20又能被2整除，又得重复上述的步骤，是不是很像递归？没错，个人认为递归很容易实现该逻辑！
最后，要求对质因子进行排列，是否可以利用有序可重复集合List的相关特性？

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int number = sc.nextInt();
            List list = new ArrayList<>();
            Main.getFactor(list, number);

            Collections.sort(list);
            System.out.print(number + "=");
            for (int i = 0; i < list.size(); i++) {
                if (i == list.size() - 1) {
                    System.out.println(list.get(i));
                } else {
                    System.out.print(list.get(i) + "*");
                }
            }
        }
        sc.close();
    }

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

从上述结果来看，已经基本满足我们的预期，接下里就是改进代码，提高效率，那么有哪些地方需要改进的呢？我认为有如下几个地方：

• 递归返回类型

这里的返回类型是int，但是并没有使用到返回值，这里可以改动（个人认为无伤大雅，无所谓！）

private static void getNum(List list, int number) {
    for (int i = 2; i < number; i++) {
        if (number % i == 0) {
            list.add(i);
            getNum(list, number / i);
            // 这个'return'必须加，你知道是为什么吗？
            return;
        }
    }
    list.add(number);
}

• 除数的范围

在上述代码中，除数i的范围取得是int i = 2; i < number; i++，其实可以发现：i不可能大于number / 2，因此可以缩短这个i的取值范围为int i = 2; i < number / 2 + 1; i++，当然，这里不更改范围也是无所谓的，因为等不到i取到一半的范围，递归就已经终止！

• 质因子的排序

从上述代码看，i是从2开始递增，并被添加到List中，因List为有序集合，所以这个List已经按照加入的顺序即从小到大的顺序排列好，因此这里无需使用Collections.sort(list)进行排序，甚至可以不用List来临时存储质因子，况且刚好题目中要求是从小到大而非从大到小！

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int number = sc.nextInt();
            System.out.print(number + "=");
            Main.getFactor(number);
        }
        sc.close();
    }

    // 这里使用的返回类型为int（个人认为最后一行'return number;'更能体现出递归的终止条件！）
    private static int getFactor(int number) {
        for (int i = 2; i < number / 2 + 1; i++) {
            if (number % i == 0) {
                System.out.print(i + "*");
                return Main.getFactor(number / i);
            }
        }
        System.out.println(number);
        return number;
    }
}

此方案仅供参考，欢迎补充回复更多更好的方案！