Java质数求解语义错误排查：埃氏筛误判合数问题求助

我完全明白你遇到的这个糟心问题——明明是合数的15、25、35却被当成质数，改了好几次代码都没搞定对吧？别慌，咱们一步步来排查问题，再给出修复后的代码和优化点。

常见错误原因分析 #

从你描述的症状来看，大概率是筛法的核心循环逻辑出了问题，常见的几个坑：

• 外层循环终止条件错误：如果你的外层循环只遍历到Math.sqrt(x)的整数部分（比如写成i < Math.sqrt(x)），会导致像5这样的质数（当x≥25时）没被处理，它的倍数25就不会被标记为非质数。正确的终止条件应该是i*i <= x，这样能确保所有质数都被遍历到。
• 内层循环起始位置错误：如果内层循环的起始点设得太大（比如跳过了i*2、i*3这些倍数），会导致像15（3*5）这类由小质数乘积组成的合数漏标，最终被当成质数。
• 数组长度不足：如果创建的数组长度是x而不是x+1，会导致数字x本身无法被索引到，但你的问题里是15、25这类小于x的数，所以这个可能性较低，但也值得检查。

修复后的完整代码 #

下面是修正后的埃氏筛实现，同时包含了优化点，能正确标记所有合数：

import java.util.Arrays;

public class Question3 {
    // 埃拉托斯特尼筛法：返回布尔数组，索引对应数字，值为true表示是质数
    public static boolean[] sieveOfEratosthenes(int x) {
        // 处理边界情况：x小于2时没有质数
        if (x < 2) {
            return new boolean[x + 1]; // 索引0到x，默认全为false
        }
        
        boolean[] isPrime = new boolean[x + 1];
        // 初始化：先假设所有数都是质数，再标记非质数
        Arrays.fill(isPrime, true);
        // 0和1不是质数
        isPrime[0] = isPrime[1] = false;
        
        // 外层循环到sqrt(x)即可，优化循环次数
        for (int i = 2; i * i <= x; i++) {
            // 只有当前i是质数时，才标记它的倍数
            if (isPrime[i]) {
                // 从i*i开始标记，避免重复处理已被更小质数标记过的倍数
                for (int j = i * i; j <= x; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        return isPrime;
    }
    
    // 测试代码，验证结果
    public static void main(String[] args) {
        int testRange = 50;
        boolean[] primes = sieveOfEratosthenes(testRange);
        
        System.out.println("1到" + testRange + "的质数列表：");
        for (int num = 2; num <= testRange; num++) {
            if (primes[num]) {
                System.out.print(num + " ");
            }
        }
        
        // 验证问题中的合数是否被正确标记
        System.out.println("\n15是质数？" + primes[15]); // 输出false
        System.out.println("25是质数？" + primes[25]); // 输出false
        System.out.println("35是质数？" + primes[35]); // 输出false
    }
}

实现的优化说明 #

这里做了几个关键优化，既保证正确性又提升效率：

• 外层循环截断到sqrt(x)：任何合数的最小质因数一定不大于它的平方根，所以遍历到i*i <= x就足够，不需要遍历到x，能大幅减少循环次数。
• 内层循环从i*i开始：i的倍数中，i*2到i*(i-1)已经被比i小的质数标记过了（比如5*2=10已经被2标记），从i*i开始标记能避免重复操作，提升筛法效率。
• 边界情况处理：提前处理x<2的情况，避免不必要的初始化和循环，让代码更健壮。

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