Java实现质数筛选替代Ruby require prime功能求助

要解决这个问题，核心是先生成maxPrimeToCube（2143）范围内的所有质数，再用这些质数来遍历计算，而不是遍历所有整数。最适合的方法是埃拉托斯特尼筛法，这是一种高效的质数生成算法，对于2143这样的小范围来说性能极佳。

步骤说明： #

• 用筛法生成2到2143之间的所有质数，存储在列表中
• 遍历质数列表中的每个质数作为q（对应原代码的primeToCube），计算q³
• 再遍历质数列表中的每个质数作为p（对应原代码的primeToSquare），计算p²
• 后续的数值范围判断、全数字检查逻辑保持不变

修改后的完整代码： #

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class PrimePairFinder {
    public static void main(String[] args) {
        long maxNum = 9876543210L;
        int minNum = 1023456789;
        int maxPrimeToCube = 2143;
        int count = 0;

        // 生成2到maxPrimeToCube之间的所有质数（埃拉托斯特尼筛法）
        List<Integer> primes = sieveOfEratosthenes(maxPrimeToCube);

        // 遍历所有质数q（用于立方）
        for (int q : primes) {
            long cubedVal = (long) q * q * q; // 用long避免溢出

            // 遍历所有质数p（用于平方）
            for (int p : primes) {
                long squaredVal = (long) p * p;
                long combinedVal = squaredVal + cubedVal;

                if (combinedVal < minNum) {
                    continue;
                }
                if (combinedVal > maxNum) {
                    break;
                }

                String s = String.valueOf(combinedVal);
                Set<Character> uniqueDigits = new HashSet<>();
                for (char digit : s.toCharArray()) {
                    uniqueDigits.add(digit);
                }

                if (uniqueDigits.size() == 10) {
                    count++;
                    System.out.printf("val: %s = %d^2 + %d^3, count: %d%n", s, p, q, count);
                }
            }
        }
        System.out.println("总符合条件的有序对数量：" + count);
    }

    // 埃拉托斯特尼筛法实现
    private static List<Integer> sieveOfEratosthenes(int max) {
        boolean[] isPrime = new boolean[max + 1];
        // 初始化所有大于等于2的数为质数
        for (int i = 2; i <= max; i++) {
            isPrime[i] = true;
        }

        // 标记非质数
        for (int i = 2; i * i <= max; i++) {
            if (isPrime[i]) {
                // 从i*i开始，标记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;
    }
}

关键改进点： #

1. 质数生成：sieveOfEratosthenes方法高效生成指定范围内的质数，避免了遍历非质数的无效计算
2. 类型安全：将cubedVal、squaredVal、combinedVal改为long类型，避免整数溢出（比如2143³已经超过int的最大值）
3. 代码结构优化：类名改为有意义的PrimePairFinder，提升可读性

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