题解 | #质数因子#

import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    
    public static List<Integer> list=new ArrayList<>();

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int a = in.nextInt();
        getPrimer(a);
        for(int i=0;i<list.size();i++){
            System.out.print(list.get(i));
            if(i<list.size()-1){
                System.out.print(" ");
            }
        }
    }
    public static void getPrimer(int a){
        
        for(int i=2;a>1;){
            if(i>Math.sqrt((double)a)){
                list.add(a);
                break;
            }
            if(a%i==0){
                list.add(i);
                a=a/i;
            }else{
                i++;
            }
        }
    }
}

超时问题的关键在于某些质数根本没有因子，所以必须要一直计数到这个质数本身，如果质数本身就很大，就会导致超时。

这时候无非有两种方法缩短时间，一个是放大因子，另一个就是缩短质数。

放大因子的思路：

计数不必再从2重新开始，因为计数本身就是从小到大开始的，那些小于当前数的整数没必要再重新遍历。

此思路只能减少起始的几个数，如果质数整体很大，依然超时。

缩短质数的思路：

这里需要利用质数的算术平方根性质，如果一个质数能被整除，那么必然会出现一对整数。这两个整数必然一个大于等于质数的平方根，另一个小于等于质数的平方根。

所以我们可以直接让因子累计到算术平方根为止，因为当你遍历完小于等于算术平方根的整数发现还不能整除时，必然不可能出现大于等于的算术平方根的整除数。

借鉴了其他大佬的思路，补充了一下为什么使用算术平方根的原理。