题解 | #质数因子#

利用筛选法 进行求解质数因子

该题为大素数问题，如果采用传统的算法：
即先利用是否能被除1和自身之外的数整除判断是否为素数，然后进行打印素数表，最后依次判断是否为因子，这样会超时

不妨利用筛选法进行素数表的获取
即初始素数设为2，则把可以被2整除的数筛选掉，这些数均不是素数，然后再遍历3，再把可以被3整除的数筛掉
即对于任一个数n，如果没被筛选掉，则意味着之前2到n-1都不可整除，则为素数

这里可以直接进行筛选，即从2开始遍历，若可以被2整除，则一直整除2，直到不可以被2整除为止，这也就把可以被2整除的数筛选掉了，对于任一遍历到的i，若不可以被n整除，则代表之后的可以整除i的数（这些数不为质数）也不可以被n整除，直接跳过即可，这样就保证每次遍历到满足n%i==0的i均为质因数

import java.util.*;
public class Main {
    public static void main(String[] args){
        List<Integer> ans = new ArrayList<>();
        Scanner scanner = new Scanner(System.in);
        long n = scanner.nextLong();
        long k = (long) Math.sqrt(1.0 * n);
        for(long i = 2; i <= k; i++){
            while(n % i == 0){
                System.out.print(i + " ");
                n /= i;
            }
        }
        System.out.print(n == 1 ? "" : n + " ");

    }      
}