简介这份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)。n10^7 时大约是 3×10^10 次取模运算普通笔记本要跑几十秒到几分钟。筛法换了个方向从 2 开始如果当前数没被标记它就是素数然后把它的所有倍数标记为合数。每个合数会被它的质因子标记不需要对每个数做除法。标记操作是数组随机写入比取模快得多。埃氏筛的时间复杂度是 O(n log log n)n10^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 乘法溢出成负数导致循环提前退出把合数误判成素数。方法时间复杂度n10^7 大致操作量额外空间典型用途单个数试除O(sqrt n)约 3×10^3O(1)判断个别数全体试除O(n sqrt n)约 3×10^10O(1)入门写法埃氏筛O(n log log n)约 2.7×10^7O(n)求 n 以内全部素数线性筛O(n)约 10^7O(n)需要质数表或积性函数分段筛O(n log log n)约 2.7×10^7O(sqrt n 段长)n 大到放不下数组表里能看出n 上到 10^7 以后决定能不能跑起来的是空间而不是时间。2.2 boolean[] 与 BitSetn 到多大要换结构Java 里最直观的标记结构是 boolean[]下标就是数值初始 false 先当素数true 表示合数。问题在于 boolean 数组每个元素通常占 1 个字节n10^8 就要约 100 MB默认堆不大的容器里很容易撞上上限抛 OutOfMemoryError。BitSet 内部用 long[] 存位每个标记只占 1 比特同样的 n 只要约 12.5 MB直接小 8 倍。结构每元素占用n10^8 标记空间随机访问遍历输出boolean[]1 字节约 100 MB最快最快BitSet1 比特约 12.5 MB位运算稍慢稍慢只存奇数的 byte[]约 0.5 字节约 50 MB快需要索引换算需要索引换算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内层循环根本不会执行。// 基础埃氏筛返回长度 n1 的 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返回数组长度 n1(long) i * i n防止 i 接近 46341 时 int 乘法溢出。内层 j 用 int 不会溢出因为进入循环时 ii 已经不超过 n。提示如果 n 可能为 0new 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); ListInteger 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 实现只要替换标记结构。参数说明n100 时要输出 25 个素数这个数量可以直接当断言primes.size()和具体列表都能肉眼核对。3.2 n、n1、i*i三个最容易写错的参数位置正确取值原因写错的后果数组长度n 1下标要能取到 n写成 n访问下标 n 时越界外层上界i * i n合数的最小质因子不超过 sqrt(n)写成 i n结果对但做大量无用功内层起点i * i小于 i*i 的倍数已被更小素数标记写成 2*i结果对但重复标记0 和 1显式置 true筛法只处理 2 的数n 为 0 或 1 时逻辑不完整注意i * i n里的乘法要用(long)提升否则 n 接近 Integer.MAX_VALUE 时 i*i 溢出成负数条件恒成立循环失控。3.3 BitSet 版本内存从约 100 MB 压到约 12.5 MBimport 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 MB256 MB 堆留有充足余量同样规模用 boolean[] 约 100 MB在更小的堆上容易失败。参数说明-Xmx256m设置最大堆n100_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否则试除法自身耗时反而成为瓶颈对拍通过只能说明在测试范围内一致正式使用前至少覆盖 n0、1、2、3、100、10000 这几个边界。4. 筛选法求素数的常见坑与 Java 面试八股追问4.1 下标越界、i*i 溢出与 0/1 处理// 错误示范三个坑同时出现 boolean[] badSieve(int n) { boolean[] p new boolean[n]; // 坑 1长度少 1n 为素数时越界 for (int i 2; i * i n; i) { // 坑 2i*i 可能溢出 if (!p[i]) { for (int j i * 2; j n; j i) { // 坑 3j n 漏掉 n且从 2*i 重复标记 p[j] true; } } } return p; }逻辑说明这段代码在 n2 时直接抛异常因为数组长度 2访问 p[2] 越界在 n 很大时i * i溢出会让外层循环多跑内层j n和j i * 2分别导致漏掉上界、重复标记。参数说明修正方式是长度取 n1、外层用(long) i * i n、内层从 i*i 开始并用j n。4.2 只筛奇数把标记量砍半的写法// 只处理奇数索引 k 对应数值 2*k1 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 2k1所以素数判断要看!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/2n2 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/21 是保守上界(long) i * primes[k] n防溢出返回的是截断后的素数表。Java 面试题里被问「埃氏筛和线性筛怎么选」可以答只要素数本身埃氏筛够用代码短如果要顺便做积性函数筛选或者 n 大到重复标记成为瓶颈线性筛的每个合数一次标记更合适。4.4 n10^8 内存不够分段筛的思路把 [0, n] 切成一段一段比如每段长度 10^6。先用普通筛求出 sqrt(n) 以内的基底素数再用这些素数逐段标记区间内的倍数。这样任意时刻只需要一个段长的标记数组加 sqrt(n) 的基底数组空间从 O(n) 降到 O(sqrt n 段长)。方案标记空间适合 n 量级备注全量 boolean[]n 字节≤ 10^7代码最简单全量 BitSetn/8 字节≤ 10^8省 8 倍奇数 BitSetn/16 字节≤ 2×10^8索引映射稍绕分段筛段长 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]; ListInteger 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-L1 建议控制在 10^6 到 10^7太小会反复筛基底素数太大失去分段意义。5.2 用 CompletableFuture 等待所有分段线程都完成// 并行分段每段一个任务allOf 等待所有线程都完成 static ListInteger parallelSegmented(long L, long R, int segments) { long step (R - L segments) / segments; ListCompletableFutureListInteger 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); ListInteger 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(); ListInteger result new ArrayList(); for (CompletableFutureListInteger f : futures) result.addAll(f.join()); return result; }逻辑说明每段参数独立、没有共享可变状态天然适合并行allOf(...).join()等待所有线程都完成再按 futures 顺序合并输出仍然有序。参数说明segments 一般取 CPU 核数段数过多会放大重复筛基底素数的开销。5.3 校验与性能观察的几个具体参数跑完并行分段后至少做两个校验结果严格递增每个数用试除法复核。区间 [1, 10^7] 用 4 段跑一遍对比全量筛的个数就能发现漏筛或越界问题。段长取 10^6 时单段标记数组约 1 MBGC 压力小取 10^7 时数组约 10 MB并行度上去后总内存要跟着算。线程数可以用-XX:ActiveProcessorCount固定便于横向比较不同并行度的耗时。实际调优时先盯段长再调线程数最后看合并阶段 ArrayList 的扩容——用 n / ln(n) 预估素数个数给初始容量能少一次数组拷贝。本文还有配套的精品资源点击获取