如何高效计算大数的最大质因数？及Java程序异常排查

首先，你的程序之所以看起来“无限运行”，核心是逻辑错误导致质数判断完全失效，再加上循环范围过大导致效率极低，让程序需要运行的时间长得离谱，看起来像卡住了。我们一步步拆解问题：

1. 质数判断的核心逻辑错误 #

你写的if (i/j == 0)完全不符合质数判断的逻辑：

• 整数除法i/j得到的是商（比如7/2=3），永远不可能等于0（除非i是0，但你的i从2开始），所以这个条件永远不会触发，flag一直是false。
• 正确的判断应该是用取模运算i % j == 0，用来检查j是否能整除i——如果能整除，说明i不是质数。

2. 变量flag的初始化位置错误 #

你把flag声明在最外层，一旦某次循环把它设为true，后续所有循环都不会重置它的值，导致后面的质数判断全部失效。应该把flag的声明和初始化移到每次检查新因数i的时候，确保每次判断质数都是从头开始的。

3. 内层循环的逻辑顺序错误 #

你现在在j的循环里，每一次迭代都去检查flag并更新最大质因数，这完全不对——应该等内层循环全部跑完，确认i确实是质数（flag仍然为false）之后，再去判断是否要更新最大质因数。

4. 外层循环范围过大，效率极低 #

i <= num/2对于600851475143这个数来说，num/2是300多亿，循环要跑这么多次，哪怕逻辑正确，也需要运行极长的时间。实际上找因数只需要循环到sqrt(num)就够了，因为因数是成对出现的（比如如果i是num的因数，那么num/i也是num的因数），我们可以同时检查这两个数是否为质数，大幅减少循环次数。

修正后的代码 #

public class LargestPrimeFactor {
    public static void main(String[] args) {
        long num = 600851475143L;
        long largestPrimeFactor = 0L;

        // 只需要循环到sqrt(num)，因数成对出现
        for (long i = 2L; i * i <= num; i++) {
            if (num % i == 0) {
                // 检查i是否是质数
                if (isPrime(i)) {
                    if (i > largestPrimeFactor) {
                        largestPrimeFactor = i;
                    }
                }
                // 检查对应的另一个因数num/i是否是质数
                long pairedFactor = num / i;
                if (isPrime(pairedFactor)) {
                    if (pairedFactor > largestPrimeFactor) {
                        largestPrimeFactor = pairedFactor;
                    }
                }
            }
        }

        // 特殊情况：如果num本身是质数（比如输入是7），上面的循环不会触发，直接赋值
        if (largestPrimeFactor == 0) {
            largestPrimeFactor = num;
        }

        System.out.println(largestPrimeFactor);
    }

    // 抽离质数判断为单独方法，更清晰
    private static boolean isPrime(long n) {
        if (n <= 1) {
            return false;
        }
        if (n == 2) {
            return true;
        }
        // 偶数直接返回false，减少循环次数
        if (n % 2 == 0) {
            return false;
        }
        // 只需要循环到sqrt(n)，且只检查奇数
        for (long j = 3L; j * j <= n; j += 2) {
            if (n % j == 0) {
                return false;
            }
        }
        return true;
    }
}

额外优化点说明 #

• 把质数判断抽离成单独的isPrime方法，代码更清晰易维护；
• 在isPrime里先处理偶数和小于等于1的情况，减少不必要的循环；
• 检查因数时同时处理成对的因数，进一步提升效率；
• 处理了num本身是质数的特殊情况。

运行这个修正后的代码，就能快速得到结果6857。

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