如何优化Java中带上标的质因数分解输出性能？

原代码的核心性能瓶颈 #

1. 低效的字符串拼接：使用OUTPUT = OUTPUT + ...的方式，每次拼接都会生成新的字符串对象，当因数数量多或指数大时，内存开销和时间成本会急剧上升。
2. 冗余的遍历逻辑：逐个遍历重复的质因数（比如5出现4次就要循环4次），当某个质因数的指数极大时，循环次数会呈线性增长，导致性能“指数级”下降。
3. 重复的边界判断：多次判断是否为最后一个元素，代码冗余且增加分支判断开销。
4. 上标转换效率低：多次调用replaceAll修改全局变量，既不高效也不符合封装原则。

优化方案与实现代码 #

1. 先统计质因数出现次数（核心优化）

使用TreeMap一次性统计每个质因数的指数，同时自动按质因数从小到大排序，避免重复遍历重复因数：

// 假设FACTOR是已获取的质因数数组（如[2,2,3,3,5,5,5,5,11]）
Map<BigInteger, Integer> factorCount = new TreeMap<>();
for (BigInteger factor : FACTOR) {
    // 统计每个质因数的出现次数，不存在则默认0再加1
    factorCount.put(factor, factorCount.getOrDefault(factor, 0) + 1);
}

2. 使用StringBuilder高效拼接结果

用可变的StringBuilder替代不可变字符串的直接拼接，大幅降低内存开销和拼接时间：

StringBuilder outputBuilder = new StringBuilder();
// 处理质数情况：只有一个质因数且指数为1
if (factorCount.size() == 1 && factorCount.values().iterator().next() == 1) {
    outputBuilder.append("prime number");
} else {
    boolean isFirstFactor = true;
    // 遍历统计好的质因数与指数
    for (Map.Entry<BigInteger, Integer> entry : factorCount.entrySet()) {
        BigInteger prime = entry.getKey();
        int exponent = entry.getValue();
        
        // 非第一个质因数前添加分隔符
        if (!isFirstFactor) {
            outputBuilder.append(" · ");
        }
        // 添加质因数
        outputBuilder.append(prime);
        // 指数大于1时添加上标
        if (exponent > 1) {
            outputBuilder.append(convertToSuperscript(exponent));
        }
        isFirstFactor = false;
    }
}
// 组装最终结果
String answer = firstword + " = " + outputBuilder.toString();

3. 高效的上标转换方法

用switch-case+字符数组处理数字到上标的转换，比多次replaceAll更高效，且封装为独立工具方法：

private static String convertToSuperscript(int number) {
    char[] digits = String.valueOf(number).toCharArray();
    StringBuilder sb = new StringBuilder();
    for (char c : digits) {
        switch (c) {
            case '0': sb.append('\u2070'); break;
            case '1': sb.append('\u00b9'); break;
            case '2': sb.append('\u00b2'); break;
            case '3': sb.append('\u00b3'); break;
            case '4': sb.append('\u2074'); break;
            case '5': sb.append('\u2075'); break;
            case '6': sb.append('\u2076'); break;
            case '7': sb.append('\u2077'); break;
            case '8': sb.append('\u2078'); break;
            case '9': sb.append('\u2079'); break;
        }
    }
    return sb.toString();
}

优化效果说明 #

• 时间复杂度优化：原代码时间复杂度为O(n)（n为因数数组总长度），优化后为O(m)（m为不同质因数的数量），当某个质因数指数极大时（如10^6），性能提升极为显著。
• 内存开销降低：StringBuilder避免了大量中间字符串对象的创建，内存使用率大幅下降。
• 代码可读性提升：逻辑清晰，冗余分支减少，维护成本降低。

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