题解 | #质数因子#

解题思路：

一、理解题干所指

本题题干的文字描述很容易让人造成误解，大家可能觉得只要循环找到输入整数的因素然后判断是否为质数就大工告成了，这种方法找到的确实是质因素，但你发现结果并不会重复，但题目要求的结果显然是有重复的（如180的质因子为2 2 3 3 5 ），那这是个什么算法呢？

实际上该题的底层逻辑是依据算数基本定理得来的：

算术基本定理 任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。

所以题目想要的是输入一个整数，然后对其进行因式分解，分解为几个质数之积，然后按从小到大的顺序打印出来，理解了该思路解题就容易了大半。

二、分解算法

如何分解

例如180，除了1和自身，我们要试图从2递增作为因素开始分解目标，

• 180=2*90,2是质数，同样算法(递归)分解另一个非质数因数90
• 90=2*45 ,2是质数，同样算法(递归)分解另一个非质数因数45
• 45=3*15 ,3是质数，同样算法(递归)分解另一个非质数因数15
• 15=35 ,3是质数，5也是质数，分解结束，递归结束：两个因素都是质数 最终180分解为 2233*5 ， 最后如果输入整数本身就是一个质数，那么直接将其打印出来即可

三、质数判断算法

判断一个数是否为质数最容易想到的算法是从2到自身循环，用自身对这些数求余，如果找到一个余数为0，则不是质数，该算法最大的问题数当输入很大的时候算法复杂度是O(n)的，时间上无法满足。

原理

根据数论我们知道，自然数是由质数、合数、1和0组成的，如果一个数是合数,那么它的最小质因数肯定小于等于他的平方根

证明：n>0 , 设n的最小的质因数是p，则q=n/p也是n的因数。又因p是最小的质因数，所以p <= q=n/p 推出 p<=sqrt(n)。 跟据该结论，我们可以在2->sqrt(n)之间寻找质因素，如果找到了则肯定是合数，否则就是质数，这样一来可以将算法的时间复杂度减少到O(sqrt(n)),时间上减少一半甚至更多

public static boolean isPrimeNumber(long val) {
        for (int i = 2; i <= Math.sqrt(val); i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
}

完整代码如下（Java实现）

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLong()) { // 注意 while 处理多个 case
            long value = in.nextLong();
            printPrime(value);
        }

    }

    private static void printPrime(long value) {
        long factor = 0;
        for (int i = 2; i < value; i++) {
            if (value % i == 0) {
                //i是value的因素，判断其是否为质数
                if (isPrimeNumber(i)) {
                    System.out.print(i + " ");
                    factor = value / i;
                    if (!isPrimeNumber(factor)) {//如果因素不是质数则继续分解
                        printPrime(factor);
                    } else {
                        System.out.print(factor + " ");
                    }
                    break;
                }
            }
        }
        if (factor == 0) {
            System.out.println(value);
        }
    }

    public static boolean isPrimeNumber(long val) {
        for (int i = 2; i <= Math.sqrt(val); i++) {
            if (val % i == 0) {
                return false;
            }
        }
        return true;
    }
}