如何分解质因数？

题目描述：

将一个正整数分解质因数。例如：输入90，打印出90 = 2 * 3 * 3 * 5。

概念梳理：

什么是质数？

质数(Prime Number)，是指在大于1的自然数中，只能被1和它本身整除的自然数。

如何判断整除？

给定除数n和被除数N，如果N / n的余数为零，则称N能被n整除。
在编程中，可用取模运算判断整除问题。

什么叫分解质因数？

即将一个合数写成几个质数相乘的形式，就叫做分解质因数。

思路分析：

1. 根据质数的定义，实现一个算法，用于判断一个自然数是不是质数；
2. 找出1~N中所有的质数；
3. 循环判断N能否被1~N中的质数整除，如果能被整除，则该质数为N的一个质因数；
4. 拿到第3步整除后的结果，重复执行第2、3两步，直到整除的结果也是一个质数为止。

代码实现：

1. 判断一个数是否为质数

/**
 * 判断一个是否为质数
 * 如果一个数n只能被1或n整除，则该数为质数，即：
 * 如果一个数n不能被1~n之间的任何数整除，则该数为质数。
 */
public boolean isPrimeNumber(int n) {
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

2. 递归分解质因数

public void factoringNumber(int n) {
    if (isPrimeNumber(n)) {
        System.out.print(n); // 直到n为质数，分解质因数完成
        return;
    }
    for (int i = 2; i < n; i++) {
        if (isPrimeNumber(i)) { // i是否为质数
            if (n % i == 0) { // n 能否被i整除
                System.out.print(i + " * ");
                int result = n / i; // 整除后的结果
                factoringNumber(result); // 递归分解质因数
                break; // 注意：找到一个质因数后即退出循环
            }
        }
    }
}

3. 分解质因数测试

factoringNumber(1001); // 7 * 11 * 13

总结：

解决问题，第一步要做的就是弄清除题目中的各个基本概念。如果基本概念不清楚，是很难正确地思考的。

比如本题中，首先要弄清的就是质数、整除、余数、分解质因数等概念。对基本概念有了深入的理解后，解决问题起来就如虎添翼了。

题目里有一个值得注意的地方，就是在找到一个质因数后，要退出循环，否则会循环会继续执行。

遇到代码执行结果与预期结果不符时，要冷静分析，只需要按照代码逻辑(Debug)在大脑里执行一遍即可。