Java筛选法求素数：埃氏筛、BitSet、线性筛与分段并行优化

简介：这份PDF文档围绕Java使用筛选法求n以内素数展开，面向正在学习算法基础、准备课程实验或面试刷题的Java开发者与在校学生。内容以埃拉托斯特尼筛法为主线，给出可直接参考的AratosternyAlgorithm示例，从数组标记0和1的状态约定讲起，逐步完成2到√n的倍数筛除，并演示按每行10个输出素数结果的写法。压缩包内仅1个PDF文件，约32KB，轻量便于下载后离线查阅与代码摘录。文档还讨论时间复杂度O(n log log n)、空间复杂度O(n)，以及n过大时受JVM内存限制、可改用位图法优化等排错思路，帮助读者理解筛选边界、参数校验和格式化输出等细节。目前已有5860人学习下载，适合希望把数学原理落到Java实现、快速掌握素数筛法核心代码与优化方向的读者参考。

1. 求 n 以内的素数，为什么试除法一上规模就歇菜

面试让手写求 n 以内的素数，不少人条件反射写双重循环试除：n 到 10^6 还能忍，再到 10^7 基本几十秒起步。换成筛选法（埃拉托斯特尼筛），同一台机器往往几十到几百毫秒出结果。

差距不在 Java 语法，而在有没有把已确认的素数当成后续合数的删除依据——每找到一个素数，就把它的倍数整批划掉，而不是对每个数单独做除法。

Java 使用筛选法求 n 以内的素数，要回答的不只是 for 循环怎么写，还有 n 大时用数组还是 BitSet、i 筛到哪停、内存不够怎么分段。下面从原理、数据结构选型一路写到线性筛与并行分段筛的代码，刚接触 Java 基础的人能照着跑，准备 Java 面试八股的人也能把复杂度与边界答完整。

2. 埃拉托斯特尼筛法的原理与 Java 数据结构选型

2.1 从试除法到筛法：复杂度差在哪

判断单个数 x 是不是素数，试除法要把 2 到 sqrt(x) 挨个除一遍，复杂度 O(sqrt x)。如果要列出 n 以内所有素数，对每个数都做一次，总代价 O(n sqrt n)。n=10^7 时大约是 3×10^10 次取模运算，普通笔记本要跑几十秒到几分钟。

筛法换了个方向：从 2 开始，如果当前数没被标记，它就是素数，然后把它的所有倍数标记为合数。每个合数会被它的质因子标记，不需要对每个数做除法。标记操作是数组随机写入，比取模快得多。埃氏筛的时间复杂度是 O(n log log n)，n=10^7 时标记次数约 2.7×10^7，量级完全不同。

// 试除法判断单个整数是否为素数 static boolean isPrimeByTrial(int x) { if (x < 2) return false; // 0、1 和负数都不是素数 for (int d = 2; (long) d * d <= x; d++) { // 用 long 乘避免 d*d 溢出 if (x % d == 0) return false; // 找到因子，直接判定为非素数 } return true; }

逻辑说明：d 从 2 试到 sqrt(x)，只要有一个整除就返回 false。参数说明：x 是待判定整数；(long) d * d用于在 x 接近 Integer.MAX_VALUE 时避免 int 乘法溢出成负数，导致循环提前退出，把合数误判成素数。

表里能看出，n 上到 10^7 以后，决定能不能跑起来的是空间而不是时间。

2.2 boolean[] 与 BitSet：n 到多大要换结构

Java 里最直观的标记结构是 boolean[]，下标就是数值，初始 false 先当素数，true 表示合数。问题在于 boolean 数组每个元素通常占 1 个字节，n=10^8 就要约 100 MB；默认堆不大的容器里很容易撞上上限，抛 OutOfMemoryError。BitSet 内部用 long[] 存位，每个标记只占 1 比特，同样的 n 只要约 12.5 MB，直接小 8 倍。

import java.util.BitSet; // 用 BitSet 做标记：bit 为 1 表示合数 static BitSet sieveWithBitSet(int n) { BitSet composite = new BitSet(n + 1); composite.set(0, 1); // 0 不是素数；set(from, to) 左闭右开 if (n >= 1) composite.set(1); // 1 不是素数 for (int i = 2; (long) i * i <= n; i++) { if (!composite.get(i)) { // i 仍是素数 for (int j = i * i; j <= n; j += i) { composite.set(j); // 标记 i 的倍数为合数 } } } return composite; }

逻辑说明：BitSet.get(i) 返回 true 表示 i 已被标记为合数，false 表示暂时是素数；标记倍数时还是用循环，因为 BitSet 的区间 set 只能按步长 1 置位，不能直接标记等差序列。参数说明：n 是上界；composite.set(0, 1) 把下标 0 置位，等价于把 0 标成合数；n 小于 1 时只处理下标 0。

选型上我一般这样定：n 不超过 10^7 用 boolean[]，代码最好读；n 在 10^7 到 10^8 之间换 BitSet，或者只存奇数；n 再往上就别一次性开数组，直接分段。

2.3 为什么 i 只筛到 sqrt(n)：边界推导与最小示例

如果 m 是合数且 m <= n，那么 m 可以写成 a * b，其中 a <= b，于是 a <= sqrt(m) <= sqrt(n)。这意味着 m 一定会在处理某个不超过 sqrt(n) 的素数时被标记。反过来，i 超过 sqrt(n) 之后，它的最小倍数 i*i 已经大于 n，内层循环根本不会执行。

// 基础埃氏筛：返回长度 n+1 的 boolean 数组，true 表示对应下标不是素数 public static boolean[] sieve(int n) { boolean[] isComposite = new boolean[n + 1]; if (n >= 0) isComposite[0] = true; // 0 不是素数 if (n >= 1) isComposite[1] = true; // 1 不是素数 for (int i = 2; (long) i * i <= n; i++) { // 只需筛到 sqrt(n) if (!isComposite[i]) { // i 是素数 for (int j = i * i; j <= n; j += i) { // 从 i*i 开始，更小的倍数已被筛过 isComposite[j] = true; } } } return isComposite; }

逻辑说明：数组下标即数值，初始 false 表示暂时认为是素数，0 和 1 单独置 true。外层 i 从 2 到 sqrt(n)，内层从 ii 开始按步长 i 推进。参数说明：n 为闭区间上界，要求 n >= 0；返回数组长度 n+1；(long) i * i <= n防止 i 接近 46341 时 int 乘法溢出。内层 j 用 int 不会溢出，因为进入循环时 ii 已经不超过 n。

提示：如果 n 可能为 0，new boolean[n + 1]仍然合法，但输出时要判断 n >= 2 才可能有素数。

3. 手写一个能跑通的 Java 筛选法求素数示例

3.1 最小可运行类：从 main 到素数表输出

import java.util.ArrayList; import java.util.List; public class PrimeSieveDemo { public static void main(String[] args) { int n = 100; boolean[] isComposite = sieve(n); List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (!isComposite[i]) primes.add(i); // 未被标记的就是素数 } System.out.println("n = " + n + ", 素数个数 = " + primes.size()); System.out.println(primes); } public static boolean[] sieve(int n) { boolean[] isComposite = new boolean[n + 1]; if (n >= 0) isComposite[0] = true; if (n >= 1) isComposite[1] = true; for (int i = 2; (long) i * i <= n; i++) { if (!isComposite[i]) { for (int j = i * i; j <= n; j += i) { isComposite[j] = true; } } } return isComposite; } }

编译运行：

javac PrimeSieveDemo.java java PrimeSieveDemo

输出：

n = 100, 素数个数 = 25 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

逻辑说明：sieve 只负责标记，主方法负责收集和打印，职责分开后，想换 BitSet 实现只要替换标记结构。参数说明：n=100 时要输出 25 个素数，这个数量可以直接当断言；primes.size()和具体列表都能肉眼核对。

3.2 n、n+1、i*i：三个最容易写错的参数

注意：i * i <= n里的乘法要用(long)提升，否则 n 接近 Integer.MAX_VALUE 时 i*i 溢出成负数，条件恒成立，循环失控。

3.3 BitSet 版本：内存从约 100 MB 压到约 12.5 MB

import java.util.BitSet; public class PrimeSieveBitSet { public static void main(String[] args) { int n = 100_000_000; // 10^8 BitSet composite = sieve(n); int count = 0; for (int i = 2; i <= n; i++) { if (!composite.get(i)) count++; } System.out.println("n = " + n + ", 素数个数 = " + count); } static BitSet sieve(int n) { BitSet composite = new BitSet(n + 1); composite.set(0, 1); if (n >= 1) composite.set(1); for (int i = 2; (long) i * i <= n; i++) { if (!composite.get(i)) { for (int j = i * i; j <= n; j += i) { composite.set(j); } } } return composite; } }

运行命令里显式给堆上限，可以观察空间是否真的够：

javac PrimeSieveBitSet.java java -Xmx256m PrimeSieveBitSet

逻辑说明：BitSet 只存位，10^8 个标记大约 12.5 MB，256 MB 堆留有充足余量；同样规模用 boolean[] 约 100 MB，在更小的堆上容易失败。参数说明：-Xmx256m设置最大堆；n=100_000_000 时素数个数是 5761455，可以用来核对实现是否正确。

3.4 和试除法对拍：确认筛选法没有漏筛或误筛

// 小范围对拍：筛法结果逐个与试除法比较 static void checkSieve(int n) { boolean[] isComposite = sieve(n); for (int x = 2; x <= n; x++) { boolean bySieve = !isComposite[x]; boolean byTrial = isPrimeByTrial(x); if (bySieve != byTrial) { throw new AssertionError("不一致: " + x + ", sieve=" + bySieve + ", trial=" + byTrial); } } System.out.println("n = " + n + " 对拍通过"); }

逻辑说明：对拍用小 n，把两种实现的每个结果做比较，一旦不一致立刻打印具体数值。参数说明：n 建议不超过 10^5，否则试除法自身耗时反而成为瓶颈；对拍通过只能说明在测试范围内一致，正式使用前至少覆盖 n=0、1、2、3、100、10000 这几个边界。

4. 筛选法求素数的常见坑与 Java 面试八股追问

4.1 下标越界、i*i 溢出与 0/1 处理

// 错误示范：三个坑同时出现 boolean[] badSieve(int n) { boolean[] p = new boolean[n]; // 坑 1：长度少 1，n 为素数时越界 for (int i = 2; i * i <= n; i++) { // 坑 2：i*i 可能溢出 if (!p[i]) { for (int j = i * 2; j < n; j += i) { // 坑 3：j < n 漏掉 n，且从 2*i 重复标记 p[j] = true; } } } return p; }

逻辑说明：这段代码在 n=2 时直接抛异常，因为数组长度 2，访问 p[2] 越界；在 n 很大时i * i溢出会让外层循环多跑；内层j < n和j = i * 2分别导致漏掉上界、重复标记。参数说明：修正方式是长度取 n+1、外层用(long) i * i <= n、内层从 i*i 开始并用j <= n。

4.2 只筛奇数：把标记量砍半的写法

// 只处理奇数：索引 k 对应数值 2*k+1 static boolean[] sieveOdd(int n) { int size = (n + 1) / 2; // 覆盖 1,3,5,...,n 附近的奇数 boolean[] composite = new boolean[size]; if (size > 0) composite[0] = true; // 1 不是素数 for (int i = 3; (long) i * i <= n; i += 2) { if (!composite[i / 2]) { // i 是素数 for (int j = i * i; j <= n; j += 2 * i) { // 只标记 i 的奇数倍 composite[j / 2] = true; } } } return composite; }

逻辑说明：除 2 以外的偶数全是合数，不需要存；索引 k 与数值 value 的关系是 value = 2k+1，所以素数判断要看!composite[value/2]。参数说明：步长是 2i 而不是 i，因为奇数乘以奇数仍是奇数，奇数乘以偶数得到偶数，不用标记；输出时 2 要单独加上，不能从数组里直接读出来。这个写法把空间和时间都压到大约一半。

4.3 线性筛：每个合数只被最小质因子标记一次

import java.util.Arrays; // 线性筛（欧拉筛）：返回 n 以内的所有素数 static int[] linearSieve(int n) { int[] primes = new int[n / 2 + 1]; // 素数个数不超过 n/2（n>=2） boolean[] composite = new boolean[n + 1]; int count = 0; for (int i = 2; i <= n; i++) { if (!composite[i]) primes[count++] = i; for (int k = 0; k < count && (long) i * primes[k] <= n; k++) { composite[i * primes[k]] = true; if (i % primes[k] == 0) break; // 保证每个合数只被最小质因子筛一次 } } return Arrays.copyOf(primes, count); }

逻辑说明：内层循环用已找到的素数去乘 i，筛掉合数；if (i % primes[k] == 0) break;是核心，设 p = primes[k]，当 p 整除 i 时，继续用更大的素数 q 去乘 i 得到的合数，其最小质因子仍然是 p，留着之后会被重复标记，所以提前退出。参数说明：primes 数组开 n/2+1 是保守上界；(long) i * primes[k] <= n防溢出；返回的是截断后的素数表。

Java 面试题里被问「埃氏筛和线性筛怎么选」，可以答：只要素数本身，埃氏筛够用，代码短；如果要顺便做积性函数筛选，或者 n 大到重复标记成为瓶颈，线性筛的每个合数一次标记更合适。

4.4 n=10^8 内存不够：分段筛的思路

把 [0, n] 切成一段一段，比如每段长度 10^6。先用普通筛求出 sqrt(n) 以内的基底素数，再用这些素数逐段标记区间内的倍数。这样任意时刻只需要一个段长的标记数组加 sqrt(n) 的基底数组，空间从 O(n) 降到 O(sqrt n + 段长)。

分段筛的难点不在原理，而在每段起始下标的对齐、小于段起点的素数不能误标，以及 0/1 的边界处理。这三点会在下一章展开。

5. 进阶落地：分段筛与并行筛的 Java 实现技巧

5.1 分段筛核心：先筛小素数，再逐段标记

import java.util.*; // 分段筛：返回 [L, R] 闭区间素性，下标 0 对应 L static boolean[] segmentedSieve(long L, long R) { int limit = (int) Math.sqrt(R) + 1; boolean[] small = new boolean[limit + 1]; List<Integer> base = new ArrayList<>(); for (int i = 2; i <= limit; i++) { if (!small[i]) { base.add(i); for (int j = i * i; j <= limit; j += i) small[j] = true; } } boolean[] isPrime = new boolean[(int) (R - L + 1)]; Arrays.fill(isPrime, true); for (int p : base) { long start = Math.max((long) p * p, (L + p - 1) / p * p); for (long m = start; m <= R; m += p) isPrime[(int) (m - L)] = false; } if (L <= 1) { for (long x = L; x <= Math.min(R, 1); x++) isPrime[(int) (x - L)] = false; } return isPrime; }

逻辑说明：先筛出 sqrt(R) 以内的基底素数，再用它们标记 [L,R] 内的倍数。start同时取 p*p 和「不小于 L 的第一个 p 的倍数」的较大值，避免把区间内的 p 本身误标。参数说明：段长 R-L+1 建议控制在 10^6 到 10^7，太小会反复筛基底素数，太大失去分段意义。

5.2 用 CompletableFuture 等待所有分段线程都完成

// 并行分段：每段一个任务，allOf 等待所有线程都完成 static List<Integer> parallelSegmented(long L, long R, int segments) { long step = (R - L + segments) / segments; List<CompletableFuture<List<Integer>>> futures = new ArrayList<>(); for (int s = 0; s < segments; s++) { long lo = L + (long) s * step; if (lo > R) break; long hi = Math.min(R, lo + step - 1); final long fLo = lo, fHi = hi; futures.add(CompletableFuture.supplyAsync(() -> { boolean[] prime = segmentedSieve(fLo, fHi); List<Integer> local = new ArrayList<>(); for (int i = 0; i < prime.length; i++) { if (prime[i]) local.add((int) (fLo + i)); } return local; })); } CompletableFuture.allOf(futures.toArray(new CompletableFuture[0])).join(); List<Integer> result = new ArrayList<>(); for (CompletableFuture<List<Integer>> f : futures) result.addAll(f.join()); return result; }

逻辑说明：每段参数独立、没有共享可变状态，天然适合并行；allOf(...).join()等待所有线程都完成，再按 futures 顺序合并，输出仍然有序。参数说明：segments 一般取 CPU 核数，段数过多会放大重复筛基底素数的开销。

5.3 校验与性能观察的几个具体参数

跑完并行分段后，至少做两个校验：结果严格递增，每个数用试除法复核。区间 [1, 10^7] 用 4 段跑一遍，对比全量筛的个数就能发现漏筛或越界问题。段长取 10^6 时单段标记数组约 1 MB，GC 压力小；取 10^7 时数组约 10 MB，并行度上去后总内存要跟着算。线程数可以用-XX:ActiveProcessorCount固定，便于横向比较不同并行度的耗时。实际调优时先盯段长，再调线程数，最后看合并阶段 ArrayList 的扩容——用 n / ln(n) 预估素数个数给初始容量，能少一次数组拷贝。

本文还有配套的精品资源，点击获取