Project Euler第87题代码结果错误，寻求问题定位与修正

我看到你在解决Project Euler第87题时得到了错误的结果，让我们一步步找出代码里的问题：

1. 质数生成方法primeNumbersTill的循环范围错误 #

你的primeNumbersTill方法本意是生成所有小于等于n的质数，但循环条件写成了i <= Math.sqrt(n)，这会导致漏掉sqrt(n)到n之间的质数。比如当n=11时，sqrt(n)≈3.3，方法只会检查3以内的奇数，完全不会处理11这个质数。虽然在你的问题中，我们需要的质数上限分别是sqrt(5e7)、cube root(5e7)、fourth root(5e7)，但错误的循环范围还是可能漏掉部分符合条件的质数（比如接近sqrt(5e7)的质数），导致后续的平方、立方、四次方列表不完整。

正确的循环范围应该是遍历从3到n的所有奇数，不过更高效的方式是直接计算每个幂次的上限，只生成需要的质数，避免生成多余的质数浪费资源。

2. isPrime方法的循环条件错误 #

当前isPrime的循环条件是i*i < number，这会导致无法正确判断平方数的质数性。比如判断9时，i=3时3*3=9不满足<9的条件，循环直接结束，错误地返回true（9不是质数）。

正确的条件应该是i*i <= number，同时可以添加对偶数和小于等于1的数的快速判断，提升效率：

private static boolean isPrime(int number) {
    if (number <= 1) return false;
    if (number == 2) return true;
    if (number % 2 == 0) return false;
    for (int i = 3; i*i <= number; i += 2) {
        if (number % i == 0) {
            return false;
        }
    }
    return true;
}

3. 使用Math.pow导致的精度隐患 #

Math.pow返回的是double类型，虽然在本题的数值范围内可能不会出现精度丢失，但对于更大的整数，double无法精确表示所有整数（超过2^53的整数会丢失精度）。而且浮点运算的效率也不如整数乘法。

应该直接使用整数乘法来计算幂次，同时用long类型进行判断避免int溢出：

// 替换Math.pow(p,2)为p*p
if ((long) p * p < n) {
    Squares.add(p * p);
}
// 立方：p*p*p
if ((long) p * p * p < n) {
    Cubes.add(p * p * p);
}
// 四次方：p*p*p*p
if ((long) p * p * p * p < n) {
    Fourth.add(p * p * p * p);
}

4. 可选优化：使用埃拉托斯特尼筛法生成质数 #

你的质数生成方式是逐个判断奇数是否为质数，对于较大的上限来说效率较低。使用埃拉托斯特尼筛法可以一次性生成所有小于等于上限的质数，速度快很多。

修正后的完整代码 #

import java.util.*;

public class Euler87 {
    public static List<Integer> sieve(int max) {
        boolean[] isPrime = new boolean[max + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= max; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= max; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }

    public static void main(String[] args) {
        int n = 50000000;
        // 只需要生成到sqrt(n)的质数，因为更大的质数平方会超过n
        int maxPrime = (int) Math.sqrt(n);
        List<Integer> primes = sieve(maxPrime);

        Set<Integer> results = new HashSet<>();

        for (int p : primes) {
            long square = (long) p * p;
            if (square >= n) break; // 后续质数更大，平方也会更大，直接跳出
            for (int q : primes) {
                long cube = (long) q * q * q;
                if (square + cube >= n) break;
                for (int r : primes) {
                    long fourth = (long) r * r * r * r;
                    long sum = square + cube + fourth;
                    if (sum >= n) break;
                    results.add((int) sum);
                }
            }
        }

        System.out.println(results.size());
    }
}

这段修正后的代码应该能得到正确的结果，同时效率也更高。

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