一、分解质因数的方法

这个不是很难，对于任意输入的num，只要设定一个变量prime的值为2，从2往上一个一个试，如果不能整除就+1：2不能整除就试3，3不能整除就试4，4不能整除就试5……循环往复，直到num被除到剩下1为止。

由于对于任意正整数k，不能被k整除的数一定不能被k的倍数整除，例如不能被2整除则一定不能被4、6、8、……整除，因此在依次增加prime的值的过程中，每次第一个能整除num的数一定会是质数，保证了答案的正确性。

二、超大质数的判断

由于输入类型是long，因此有可能会碰到很大的质数，导致超时。为了避免超时，需要根据以下知识点对算法进行优化：

对于正整数k：

如果k是合数，则其最大的质因数不超过√k。
如果k刚好是质数的平方，则其最大质因数刚好是√k。
如果k是质数，那么比√k大且比k小的整数都不能整除k。

所以为了判断k是不是质数，如果从2开始把各个整数都作为除数试一遍，且都不能整除，那么只要最多试到√k且发现都不能整除，则k就是质数。这样对于k最多只需要试√k次就能判断它是不是质数，有效解决了超时的问题。

完整代码如下（Java）

import java.lang.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextLong()) {
            long num = sc.nextLong();
            decomp(num);
        }

        sc.close();
    }

    private static void decomp(long num) {
        List<Long> outputs = new ArrayList<Long>();
        if (num < 2) {
            return;
        }

        long prime = 2;
        while (num >= 2) {
            if (prime > Math.sqrt(num)) {
                // this means that num by itself is a prime
                // this trick is used for very large primes
                prime = num;
            }

            if (num % prime == 0) {
                num /= prime;

                System.out.print(prime);
                System.out.print(" ");
            }
            else {
                ++prime;
            }
        }
        System.out.println();
    }
}

题解 | #质数因子#

一、分解质因数的方法

二、超大质数的判断

完整代码如下（Java）