如何实现支持指定起始值的Eratosthenes筛法Java程序？

嘿，我懂你现在卡在哪了——原本的埃氏筛默认从2开始筛素数，但要改成筛选[start, end]区间内的素数，直接改起始点很容易踩坑，比如start本身是合数的时候，筛法的标记逻辑就会乱套，导致输出异常。下面给你两种可行的解决方案，按需选用就行。

为什么直接改起始值会出问题？ #

标准埃氏筛的核心逻辑是用已找到的小素数标记所有其倍数，如果直接从start开始筛，会漏掉小于start的素数对[start, end]区间内合数的标记。比如start=10，因子2小于10，如果不从2开始筛，就不会标记10、12这些区间内的合数，导致错误地把它们当成素数。

方案一：基础版（简单易理解，适合end不大的场景） #

先筛出2到end的所有素数，再从中过滤出落在[start, end]区间内的结果。这种方法逻辑简单，不容易出错，完全能满足作业需求。

import java.util.ArrayList;
import java.util.List;

public class RangeSieve {
    public static List<Integer> getPrimesInRange(int start, int end) {
        // 处理无效输入
        if (start > end || end < 2) {
            return new ArrayList<>();
        }

        // 第一步：用标准埃氏筛生成2到end的素数标记数组
        boolean[] isPrime = new boolean[end + 1];
        for (int i = 2; i <= end; i++) {
            isPrime[i] = true;
        }
        for (int p = 2; p * p <= end; p++) {
            if (isPrime[p]) {
                // 从p的平方开始标记倍数（更小的倍数已被之前的素数标记）
                for (int i = p * p; i <= end; i += p) {
                    isPrime[i] = false;
                }
            }
        }

        // 第二步：筛选出[start, end]区间内的素数
        List<Integer> result = new ArrayList<>();
        // 小于2的数没有素数，所以起始点取start和2的最大值
        int actualStart = Math.max(start, 2);
        for (int i = actualStart; i <= end; i++) {
            if (isPrime[i]) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试示例：筛选10到30之间的素数
        int start = 10;
        int end = 30;
        List<Integer> primes = getPrimesInRange(start, end);
        System.out.printf("[%d, %d]区间内的素数：%n", start, end);
        System.out.println(primes);
    }
}

方案二：分段筛法（适合end极大的场景） #

如果end特别大（比如超过10^6），基础版会占用过多内存。这时候可以用分段筛：先筛出sqrt(end)以内的所有素数，再用这些素数标记[start, end]区间内的合数，内存占用会小很多。

import java.util.ArrayList;
import java.util.List;

public class SegmentedSieve {
    // 辅助方法：筛出limit以内的所有素数
    private static List<Integer> simpleSieve(int limit) {
        boolean[] isPrime = new boolean[limit + 1];
        for (int i = 2; i <= limit; i++) {
            isPrime[i] = true;
        }
        for (int p = 2; p * p <= limit; p++) {
            if (isPrime[p]) {
                for (int i = p * p; i <= limit; i += p) {
                    isPrime[i] = false;
                }
            }
        }
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i <= limit; i++) {
            if (isPrime[i]) primes.add(i);
        }
        return primes;
    }

    // 核心方法：筛选[start, end]区间内的素数
    public static List<Integer> getPrimesInRange(int start, int end) {
        if (start > end || end < 2) {
            return new ArrayList<>();
        }

        int sqrtEnd = (int) Math.sqrt(end) + 1;
        List<Integer> basePrimes = simpleSieve(sqrtEnd);

        // 创建区间标记数组：index 0对应start，index (end-start)对应end
        boolean[] isPrimeInRange = new boolean[end - start + 1];
        // 初始化所有数为素数
        for (int i = 0; i < isPrimeInRange.length; i++) {
            isPrimeInRange[i] = true;
        }

        // 处理start<=1的情况（1不是素数）
        if (start <= 1) {
            for (int i = 0; i <= Math.min(end, 1) - start; i++) {
                isPrimeInRange[i] = false;
            }
        }

        // 用基础素数标记区间内的合数
        for (int p : basePrimes) {
            // 找到区间内第一个p的倍数（大于等于start）
            int firstMultiple = (start / p) * p;
            if (firstMultiple < start) firstMultiple += p;
            // 从p的平方开始标记（更小的倍数已被更小的素数标记）
            firstMultiple = Math.max(firstMultiple, p * p);

            // 标记所有p的倍数
            for (int i = firstMultiple; i <= end; i += p) {
                isPrimeInRange[i - start] = false;
            }
        }

        // 收集结果
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < isPrimeInRange.length; i++) {
            if (isPrimeInRange[i]) {
                result.add(start + i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        // 测试示例：筛选100到200之间的素数
        int start = 100;
        int end = 200;
        List<Integer> primes = getPrimesInRange(start, end);
        System.out.printf("[%d, %d]区间内的素数：%n", start, end);
        System.out.println(primes);
    }
}

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