题解 | #质数因子#

代码如下，注释很清楚了

import java.util.Scanner;

/**
 * @author lymili
 * @Date 2022/3/31 20:08
 * @Version 1.0
 */

// 题目：HJ6 质数因子
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
//        System.out.print("请输入一个数：");
        int number = in.nextInt();
        PrimeFactor res = new PrimeFactor();
        System.out.println(res.primeFactor1(number));
//        System.out.println(res.primeFactor(2000000014));
//        System.out.println(res.primeFactor1(2000000014));
//        System.out.println(res.primeFactor(1));
//        System.out.println(res.primeFactor1(65557));
//        System.out.println(res.primeFactor1(5));
//        System.out.println(res.primeFactor(25));
//        System.out.println(res.primeFactor1(25));
        in.close();
    }
}

class PrimeFactor{

    /**
     * 函数功能： 分解质因数，并将所有质因子（含重复）拼接成字符串返回
     * @param number 给定的数
     * @return 所有质因子构成的字符串
     */
    public String primeFactor(int number) {
        StringBuilder stringBuilder = new StringBuilder();
        int minPrime = 2;
        // 判断是否为质数，是质数直接返回。分解质因数只针对合数
        if (isPrime(number)) {
            stringBuilder.append(number).append(" ");
            return stringBuilder.toString();
        }
        while (number >= minPrime) {
            if (number % minPrime == 0) {
                stringBuilder.append(minPrime).append(" ");
                number = number / minPrime;
                minPrime = 2;
            } else {
                minPrime++;//时间复杂度很高 怎么优化？
            }
        }
        return stringBuilder.toString();
    }

    /**
     * 函数功能：同上 但是优化了超时
     * @param number 给定的数
     * @return 所有质因子构成的字符串
     */
    public String primeFactor1(int number) {
        StringBuilder stringBuilder = new StringBuilder();
        int minPrime = 2;
        int temp = number;
        // 判断是否为质数，是质数直接返回。分解质因数只针对合数
        if (isPrime(number)) {
            stringBuilder.append(number).append(" ");
            return stringBuilder.toString();
        }
//        while (minPrime <= number && minPrime < Math.sqrt(number)) {
//        while (minPrime <= number && minPrime < Math.sqrt(temp)) {
        while (minPrime <= number && minPrime <= Math.sqrt(temp)) {
            while (number % minPrime == 0) {
                stringBuilder.append(minPrime).append(" ");
                number = number / minPrime;
                // 判断是否为质数，是质数直接返回。分解质因数只针对合数
                if (isPrime(number)) {
                    stringBuilder.append(number).append(" ");
                    return stringBuilder.toString();
                }
//                minPrime = 2;
//                minPrime++;
            }
            minPrime++;
        }
        return stringBuilder.toString();
    }


    /**
     * 判断一个数是否为质数，如果是返回true
     * @param num 带判断的数
     * @return 返回 true 表示素数
     */
    public boolean isPrime(int num) {
        for (int minPrime = 2; minPrime < Math.sqrt(num) + 1; minPrime++) {
            if (num % minPrime == 0) return false;
        }
        return true;
    }
}

/*
 质因子 例如：180 = 2 x 2 x 3 x 3 x 5 （短除法）
 质数---只有1和它本身两个约数的自然数 两个条件：1.有两个约数 2.本身
 质数因子：如果该数是质数，那么质因子只有该数本身（1 既不是质数，也不是合数）
 如果该数是合数，通过短除法一定可以拆成几个质数相乘
 短除法：
 初始化：最小的质数2 给定的数 num
 1. 特殊情况，如果num = 1, 则没有质因数
 2. 如果该数是质数，那么直接输出该数
 3. 如果该数是合数，那么就用短除法除
 
 短除法超时了……
 2022/4/1 网上查找资料，发现还真得判断是否为质数
 超时优化：因为短除法是从最小的质数2开始慢慢加一，
 如果碰到一个超级大的质数N，那么就要循环N次，判断N次。

*/