如何实现返回特定格式的整数质因数分解功能？

原代码存在的问题 #

1. 条件判断冗余且顺序错误：else if(n == 2)分支永远不会执行，因为2是质数，会被isPrime(n)先匹配到。
2. 未更新被分解的数值：while(n%i==0)循环中只拼接因数，但未将n除以i，导致无限循环或无法分解后续因数。
3. 缺少因数分隔符：拼接字符串时未添加要求的*，结果会变成无分隔的数字串。
4. 遗漏剩余质数：当循环结束后，若剩余的n是大于1的质数（比如180分解到最后剩下的5），未将其加入结果。
5. 质数判断效率低：isPrime方法循环到n/2，可以优化到Math.sqrt(n)减少循环次数。

修正后的完整代码 #

public class PrimeFactorization {
    public static String factor(int n) {
        // 处理输入为1或小于1的情况，可根据需求调整返回值
        if (n <= 1) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        // 从最小质数2开始分解
        for (int i = 2; i <= Math.sqrt(n); i++) {
            while (n % i == 0) {
                if (sb.length() > 0) {
                    sb.append(" * ");
                }
                sb.append(i);
                // 更新n，继续分解剩余部分
                n = n / i;
            }
        }
        // 若最后剩余的n是大于1的质数，加入结果
        if (n > 1) {
            if (sb.length() > 0) {
                sb.append(" * ");
            }
            sb.append(n);
        }
        return sb.toString();
    }

    public static boolean isPrime(int n) {
        if (n <= 1) {
            return false;
        }
        // 优化循环范围到sqrt(n)，减少不必要的判断
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

    // 测试示例
    public static void main(String[] args) {
        System.out.println(factor(180)); // 输出：2 * 2 * 3 * 3 * 5
        System.out.println(factor(7));   // 输出：7
        System.out.println(factor(49));  // 输出：7 * 7
    }
}

关键修正点说明 #

• 用StringBuilder替代String拼接，避免频繁创建字符串对象，提升效率。
• 每次匹配到因数后立即更新n = n / i，确保后续分解的是剩余的数值。
• 添加分隔符逻辑：仅当已有内容时才添加*，避免开头或末尾出现多余分隔符。
• 循环结束后检查剩余的n，确保最后一个质数被加入结果。
• 优化isPrime的循环范围，从n/2改为Math.sqrt(n)，因为若n有大于sqrt(n)的因数，必然有一个对应的小于sqrt(n)的因数，无需判断到n/2。

内容的提问来源于stack exchange，提问作者user20146539