题解 | #质数因子#

import java.io.*;
import java.util.*;

public class Main {
    /**
     * 要求n的质因子，只用遍历2~（n-1）之间的每一个整数i，
     * 如果i能被n整除，则i是n的因子；
     * 优化：如果i是n的质因子，则n必存在另一个因子j>sqrt(n)，
     * 例如：16=2*8,16=4*4，2和8分别小于大于4;因此如果在2~sqrt(n)
     * 之间没有因子，那么在sqrt(n)~n之间肯定不会有因子。
     * 所以只用遍历2~sqrt(n)之间的整数就可以了。
     * 通过n/=i，剔除已经求出的质因子，不断减小n，缩小循环次数
     *
     * @param args
     */
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        long num = scanner.nextLong();

	    //条件是i*i <= num否则会超时
	   //如果是i <= num会超时
        for (long i = 2; i * i <= num; ++i) {
            while (num % i == 0) {
                System.out.print(i + " ");
                num /= i;
            }
        }
        System.out.println(num == 1 ? "" : num + " ");
    }
}