题解 | #质数因子#

这道题可以用上一些埃拉托斯特尼筛法 (Sieve of Eratosthenes)的思路。

有三个关键点：

1. 每个合数至少有一个质因数小于或等于自身的平方根，如没有，则为质数。所以 i*i <= num

可以用反证法证明， $设 a \times b = N，如有a>\sqrt N, b > \sqrt N，则a \times b > N，与假设不符$ 。

2. 筛选法，num % i == 0时，一系列 i的倍数（也就是合数）都要被筛掉，当所有合数都被筛完，剩下的就是质数。

3. 不要忘记最后剩下的那一个质因数（num），因为他在2~sqrt(num)中都找不到可以整除他的数，符合质数只有1和自己可以整除的定义以及第一条性质。

import java.util.Scanner;

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

        int num = scanner.nextInt();
        int i = 2;
        while (i*i <= num) {
            if (num % i == 0) {
                System.out.print(i + " ");
                num /= i;
            } else {
                i++;
            }
        }
        System.out.println(num);
    }
}

其实还可以优化一下，把i的步进改为2，但是那样不简洁，没必要。

import java.util.Scanner;

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

        int num = scanner.nextInt();
        int i = 2;
        while (i*i <= num) {
            if (num % i == 0) {
                System.out.print(i + " ");
                num /= i;
            } else { // 可以拆成两个独立循环，消去这个if branch
                if (i == 2) {
                    i = 3;
                    continue;
                }
                i+=2;
            }
        }
        System.out.println(num);
    }
}