简介这份资源是一份Java算法实践文档围绕埃拉托斯特尼筛选法筛选法讲解如何在Java中求解n以内的素数面向正在学习数据结构与基础算法的初学者、准备笔试面试的开发者以及对素数判定与数组标记技巧感兴趣的编程爱好者。压缩包共1个文件为1个PDF文档体积约32KB内容以示例代码、注释解析和运行说明为主方便直接对照阅读与调试。文档给出完整的AratosternyAlgorithm类实现包括参数合法性校验、以数组下标表示数字、用0和1区分素数与合数、从2开始将素数倍数逐一标记并借助Math.sqrt(n)控制筛选上界同时采用每行输出10个素数的排版方式打印99999以内的结果并附带时间与空间复杂度分析指出n过大时受JVM内存限制可改用位图法优化。该资源已有5860人学习适合作为算法入门练习与代码复盘参考。1. 筛选法求 n 以内素数先算清「试除」这笔账很多人在 java 基础 阶段第一次写「求 n 以内的素数」套路是双重循环逐个试除外层枚举 i内层枚举 2 到 sqrt(i)一个都除不尽就输出。代码二十行思路直白n 小的时候完全够用。可问题是它把每个数都当成独立的陌生数字重新认识一遍前面积累的信息一点没用上n 涨到千万级运算量跟着一起涨。筛选法求素数换了个角度不去问「i 是不是素数」而是先认定 2 是素数然后把 2 的倍数全部划掉下一个没被划掉的数是 3再把 3 的倍数划掉如此推进到 sqrt(n)。每个合数只会被它的最小素因子划掉一次重复劳动被整体摊掉了。所以在 java 面试题 里问到「n 以内素数怎么求最快」答筛法基本是标准答案。接下来从 boolean[] 的最小可运行版本写起再换成 BitSet 省内存补上线性筛和分段筛选把 n 的边界、sqrt 的截断、p*p 的溢出、并行写入这些坑一个个说清楚。2. 埃拉托斯特尼筛法原理与第一版 java boolean[] 实现2.1 标记数组为什么能把重复判断摊薄埃拉托斯特尼筛法的核心数据结构是一个布尔标记数组下标表示数字本身值表示「这个数已经被证明是合数」。初始状态全部为 false表示暂时都还「清白」。从 2 开始向右扫描遇到第一个 false 的下标 p就断定 p 是素数——因为所有比 p 小的数都已经处理过没有任何一个能整除它随后把 p 的所有倍数标成 true。复杂度里的 log log n 来自哪里每个素数 p 要划掉大约 n/p 个数把所有素数的贡献加起来是 n 乘以「素数倒数和」而素数倒数和约等于 ln ln n。相比之下逐个试除要付出 sum(sqrt(i)) 的代价两者在 n 增长时的差距会持续拉大。另一条关键性质是外层循环只需走到 sqrt(n)任何合数 m 一定有一个不超过 sqrt(m) 的因子所以当所有不超过 sqrt(n) 的素数都划完倍数后剩下的必然全是素数。还有一个常被忽略的优化点标记可以从 pp 开始而不是从 2p 开始。因为 2p、3p、……、(p-1)p 这些更小的倍数在之前处理 2、3、…… 的时候就已经被划掉了从 pp 起步能省掉大量重复写入。2.2 可以直接跑起来的最小实现import java.util.Arrays; public class SieveDemo { // 返回 n 以内(含 n)的所有素数n 小于 2 时返回空数组 public static int[] primesUpTo(int n) { if (n 2) { return new int[0]; } boolean[] composite new boolean[n 1]; // false 表示还没被划掉 int limit (int) Math.sqrt(n) 1; // 加 1规避浮点截断 for (int p 2; p limit p n; p) { if (composite[p]) { continue; // p 已被更小的素数划掉跳过 } // 从 p*p 起步用 long 判断避免 p*p 在 int 上溢出 for (long m (long) p * p; m n; m p) { composite[(int) m] true; } } int count 0; for (int i 2; i n; i) { if (!composite[i]) { count; } } int[] result new int[count]; int k 0; for (int i 2; i n; i) { if (!composite[i]) { result[k] i; } } return result; } public static void main(String[] args) { System.out.println(Arrays.toString(primesUpTo(30))); // 输出: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] } }代码分三段理解。第一段声明boolean[] composite长度 n1 是为了让下标和数字一一对应写composite[n]不越界。第二段是筛主体的双重循环外层变量 p 走的是候选取值内层 m 走的是「被划掉的位置」m p保证了每次正好跳一个 p。第三段做两次线性扫描第一次数个数第二次数值填充到int[]——先统计再分配避免用ArrayListInteger带来装箱开销。2.3 关键参数与边界取值参数或写法常见取值作用与注意点n2 到 1e8上界数组长度为 n1n 越大内存越吃紧limit(int) Math.sqrt(n) 1外层终止条件加 1 防Math.sqrt在完全平方数上返回略小值起始倍数p * p不能写成2 * p否则前面已划过的倍数会被重复写循环变量类型long mp * p在 p 接近 46341 时会溢出 intcomposite[]语义true 表示合数命名反了最容易读错逻辑建议叫isComposite提示(int) Math.sqrt(n)是一个历史悠久的坑。Math.sqrt 走的是浮点运算对 2^53 以内的值结果虽然精确但向下取整后有可能比真实整数根小 1加 1 或直接把循环条件写成(long) p * p n都能绕开。3. 从 boolean[] 到 BitSet 与线性筛内存和速度怎么选3.1 boolean[] 到底占多少内存HotSpot 里 boolean[] 的每个元素占 1 个字节不是 1 个 bit这是很多人的第一反应会错的地方。n 取一亿时new boolean[n 1]就是约 100MB 的连续空间再加上 int[] 结果数组很容易触发 Full GC 甚至 OOM。对比之下java.util.BitSet内部用long[]存位每个标记只占 1 bit同样规模只需要约 12.5MB内存差八倍。除了省内存BitSet 还提供了两个顺手的 APInextClearBit(int fromIndex)可以直接跳到下一个未被标记的位置用来枚举素数非常自然cardinality()能一次拿到置位总数配合取反逻辑就能得到素数个数。代价是每次读写都要做「位运算 数组寻址」单次访问比 boolean[] 慢一点但在内存节省面前通常值得。3.2 用 BitSet 重写筛选逻辑import java.util.BitSet; public class BitSetSieve { // 返回 BitSet第 i 位为 true 表示 i 是合数 public static BitSet sieve(int n) { BitSet isComposite new BitSet(n 1); // 默认全为 false for (int p 2; (long) p * p n; p) { if (isComposite.get(p)) { continue; } for (int m p * p; m n; m p) { // p*p n 已保证不溢出 isComposite.set(m); } } return isComposite; } public static void main(String[] args) { int n 100; BitSet c sieve(n); StringBuilder sb new StringBuilder(); for (int i c.nextClearBit(2); i n; i c.nextClearBit(i 1)) { sb.append(i).append( ); } System.out.println(sb); // 2 3 5 7 11 ... 97 } }sieve方法把溢出判断直接放进外层循环条件(long) p * p n合法状态下内层p * p一定不会溢出于是可以省掉一次 long 转换。枚举部分用nextClearBit从当前位置往后找下一个未被标记的位比逐个get(i)的写法在稀疏区间上更快。注意BitSet会自动扩容所以下标超出预设长度不会抛异常但也意味着如果循环边界写错程序不会立刻报错而是悄悄多算一段排查时要注意核对上界。3.3 线性筛欧拉筛与埃氏筛的差别埃氏筛的短板在于同一个合数可能被多个素因子划到比如 30 会被 2、3、5 各写一次。线性筛用「每个合数只被它的最小素因子筛掉一次」的规则把复杂度压到严格 O(n)。public static int[] linearSieve(int n) { if (n 2) { return new int[0]; } boolean[] composite new boolean[n 1]; int[] primes new int[n / 2 1]; // n 2 时素数个数 n/2容量足够 int cnt 0; for (int i 2; i n; i) { if (!composite[i]) { primes[cnt] i; // i 没被筛掉它是素数 } for (int j 0; j cnt; j) { long v (long) i * primes[j]; if (v n) { break; // 超过上界后面的素数只会更大 } composite[(int) v] true; if (i % primes[j] 0) { break; // 保证 primes[j] 是 v 的最小素因子 } } } return java.util.Arrays.copyOf(primes, cnt); }if (i % primes[j] 0) break;是整段代码的灵魂一旦当前素数能整除 i说明再乘下去得到的最小素因子就不再是 primes[j]继续筛会产生重复所以必须在此处截断。线性筛的常数比埃氏筛大n 在一千万以内埃氏筛常常更快n 更大且需要频繁统计时才体现优势。3.4 三种实现的选型对照实现时间复杂度空间占用n1e8适用场景boolean[]埃氏筛O(n log log n)约 100MBn ≤ 1e7教学和小规模验证BitSet埃氏筛O(n log log n)约 12.5MBn 到 1e8内存敏感且写法想保持简单线性筛O(n)约 100MBboolean[] 加素数表需要素数表本身、或做题时要求严格线性奇偶优化只存奇数O(n log log n)约 50MB想再省一半内存又不想引入新依赖注意选型时先看 n 的量级再看常数。空间占用决定了程序能不能跑起来常数只决定跑多快顺序不要颠倒。4. 筛法结果落地素数收集、前缀计数与分段筛选4.1 把标记数组变成可用结果拿到 BitSet 之后最常见的两种落地方式是转成 int[] 和转成 List。用流式写法要注意别踩装箱坑import java.util.BitSet; import java.util.stream.IntStream; BitSet composite BitSetSieve.sieve(1_000_000); // 方式一直接得到 int[]全程走 int 流无装箱 int[] arr IntStream.rangeClosed(2, 1_000_000) .filter(i - !composite.get(i)) .toArray(); // 方式二只要前 10 个配合 limit 提前截断 int[] head IntStream.rangeClosed(2, 1_000_000) .filter(i - !composite.get(i)) .limit(10) .toArray();IntStream是基本类型流filter和toArray全程不产生Integer对象如果换成StreamInteger一百万个元素会带来明显的装箱与 GC 压力。limit放在filter之后才有意义——它会在管道里触发短路一旦凑够 10 个就不再继续扫描后面的区间这在只需要验证前几个素数时很实用。4.2 用前缀数组回答「n 以内有多少个素数」搜索「小于给定数值的素数个数」这类问题时用户要的通常不是列出素数而是快速回答区间计数。筛一遍再从前到后累加就能得到前缀计数数组之后任意查询都是 O(1)public static int[] primePrefixCount(int n) { boolean[] isComposite new boolean[n 1]; for (int p 2; (long) p * p n; p) { if (isComposite[p]) continue; for (int m p * p; m n; m p) isComposite[m] true; } int[] pi new int[n 1]; // pi[i] i 以内(含 i)素数个数 for (int i 2; i n; i) { pi[i] pi[i - 1] (isComposite[i] ? 0 : 1); } return pi; // pi[0] 与 pi[1] 天然为 0 }pi[i] pi[i - 1] 增量是前缀和的固定形态增量取 0 或 1。这样pi[100] 25、pi[1_000_000] 78498都是常数时间查询。代价是多一个 int 数组n1e7 时约 40MB如果只是偶尔查一次把统计和查询合并成一次遍历更划算。4.3 n 大到装不下时改用分段筛选当上界到 1e9 甚至 1e12再开一个规模为 n 的标记数组就不现实了。分段筛选的思路是只对小范围求种子素数再用这些种子去划目标区间。import java.util.ArrayList; import java.util.List; public class SegmentedSieve { // 返回 [low, high] 内的所有素数要求 low 2 public static ListLong sieve(long low, long high) { int root (int) Math.sqrt(high) 1; // 种子只筛到 sqrt(high) boolean[] small new boolean[root 1]; ListInteger seeds new ArrayList(); for (int i 2; i root; i) { if (small[i]) continue; seeds.add(i); for (long m (long) i * i; m root; m i) { small[(int) m] true; } } int len (int) (high - low 1); // 区间长度必须能放进 int boolean[] mark new boolean[len]; // mark[i] 表示 lowi 是合数 for (int p : seeds) { long start Math.max((long) p * p, ((low p - 1) / p) * p); for (long m start; m high; m p) { mark[(int) (m - low)] true; } } ListLong res new ArrayList(); for (int i 0; i len; i) { if (!mark[i]) res.add(low i); } return res; } }((low p - 1) / p) * p是向上取整到 p 的倍数和p * p取较大值是为了避免把种子素数本身误标成合数同时也跳过那些已经被更小素数处理过的倍数。整个算法的空间只和区间长度有关和时间无关因此可以把 1e12 分成若干段依次处理。实际使用时再把区间进一步切小配合结果落盘就能处理远超内存容量的上界。4.4 结果不对时先查这几处现象常见原因处理方式结果里混进合数外层没走到 sqrt(n)或limit被浮点截断拉小改为(long) p * p n作为循环条件数组越界m n写成m n p之类或上界用了 n 而数组长 n1核对下标与数组长度是否差一大规模 n 返回负数或不终止p * p在 int 上溢出内层变量改 long或先做 (long) 转换并行版本偶发漏标多线程写同一个 BitSet / boolean[]见下一章的切片方案提示调试时不要一上来就跑 1e8。先用 n30、n100 把输出和手算结果对齐确认边界和下标都没错再逐步放大规模。5. 进阶技巧奇偶优化、并行筛选与结果校验5.1 只存奇数的奇偶优化除 2 以外所有素数都是奇数把偶数从标记数组里彻底删掉内存直接减半循环步长也能翻倍。做法是建立映射index(i) i 1数组第 k 位对应数字2k1。// isComposite[k] 表示数字 (2k1) 是合数 public static boolean[] oddSieve(int n) { boolean[] isComposite new boolean[(n 1) 1]; for (int p 3; (long) p * p n; p 2) { if (isComposite[p 1]) continue; // 2p 是步长奇数 p 的奇数倍之间相差 2p映射到下标上正好跳 p for (int m p * p; m n; m 2 * p) { isComposite[m 1] true; } } return isComposite; }这里最容易写错的是步长数字上的步长是2p映射到下标正好是p写成p 2就会漏掉一半倍数。这个版本比 BitSet 更快代价是读代码的人需要在脑子里维护「下标和数字」的换算关系团队协作时最好在方法头一行写清映射规则。5.2 并行筛选的正确切法很多人自然想到把外层素数循环改成IntStream.rangeClosed(2, limit).parallel()这个写法有两个问题。第一filter(p - !composite.get(p))会在筛开始之前就全部执行完读到的是初始状态所有候选都会通过等于白筛一遍第二就算修好顺序BitSet.set内部是words[idx] | mask的读改写操作不是原子的两个线程命中同一个 long 字时会丢更新导致部分合数漏标结果偶尔出错且难以复现。稳妥的做法是切片并行把小素数种子先单线程算好再把目标区间切成若干互不重叠的段每段各自开一个局部标记数组独立筛选最后合并。段与段之间没有共享写不需要任何同步原语结果也完全确定。5.3 用 diff 做交叉校验换实现的时候最省事的验证路径是拿两版结果做集合比对而不是盯着耗时数字。先用 BitSet 版跑一遍拿基准再换奇偶优化版重跑把两次得到的素数集合做一次 diff全等之后再去看时间才有意义。n 取 1e6 时正确结果应包含 78498 个素数这个数字可以直接作为断言的锚点n 取 30 时结果是[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]适合放在单元测试里当小样本用例。本文还有配套的精品资源点击获取