优化最大质因数求解Java程序的最佳方法 解决运行超时问题

原代码核心问题 #

• 语法错误：类定义public class PFactor()多余括号、maxVal与max变量名不统一，本身无法编译通过
• 因数遍历边界错误：循环上限为原数d，实际因数最大不会超过sqrt(d)，冗余循环量极大
• 质数判断效率极低：pCount方法通过遍历所有数统计因数个数判断质数，单判断复杂度为O(待判断数大小)
• 未消解已找因数：找到因数后未从原数中除尽，导致大量重复判断非必要值
• 无奇偶剪枝：未排除2以外的偶数，冗余计算量翻倍

优化核心逻辑 #

采用因数成对遍历+质因数消解+奇偶剪枝的方案，时间复杂度从原O(n²)降至O(sqrt(n))：

• 先单独处理所有2的因数，后续循环仅遍历奇数，减少一半计算量
• 循环上限设为当前剩余数的平方根，避免无效遍历
• 每找到一个可整除的因子，就将该因子从当前数中除尽，同时更新最大质因数
• 无需单独判断因子是否为质数：从小到大消解因数的过程中，能整除剩余数的因子必然是质数，省去单独质数判断的开销
• 循环结束后若剩余数大于2，说明该剩余数本身为质数，即为最大质因数

优化后可直接运行的代码 #

import java.io.*;

public class PFactor {
    public static void main(String[] args) {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        try {
            int t = Integer.parseInt(br.readLine());
            for (int a0 = 0; a0 < t; a0++) {
                long n = Long.parseLong(br.readLine());
                System.out.println(getLargestPrimeFactor(n));
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public static long getLargestPrimeFactor(long d) {
        long maxPrime = -1;
        // 处理所有2的因数
        while (d % 2 == 0) {
            maxPrime = 2;
            d /= 2;
        }
        // 从3开始遍历奇数，直到平方根
        for (long i = 3; i * i <= d; i += 2) {
            while (d % i == 0) {
                maxPrime = i;
                d /= i;
            }
        }
        // 剩余大于2的数本身为质数
        if (d > 2) {
            maxPrime = d;
        }
        return maxPrime;
    }
}

额外优化点说明 #

• 输入读取改用BufferedReader，替换原Scanner，在测试用例量大时可进一步降低IO耗时
• 原返回值为int，若输入n超过int取值范围会溢出，优化后返回long，适配大数值场景
• 循环条件用i * i <= d替代i <= sqrt(d)，避免浮点运算的精度误差和额外计算开销

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