1. 从面试高频题到工程思维：为什么要认真对待“求100以内素数”
如果你准备过大厂Java后端面试，或者正在刷LeetCode、牛客网，大概率见过这道题：用Java求100以内的素数。说实话，第一次看到这道题，我也觉得“就这”？两个for循环套一套，判断一下能不能整除，不就行了。但后来我发现，这道题“水”很深——它表面考的是循环、取模、布尔标记这些Java基础语法，实际上却覆盖了算法复杂度分析、代码风格、边界条件处理、面试表达逻辑，甚至还能延伸到并发编程、加密算法这些高级话题。
先说一个我自己的经历。多年前面某大厂Java岗，前两轮算法题都顺利过了，第三轮面试官突然在纸上写了这行字：“求100以内素数，写一下。”我当时心里咯噔一下，倒不是不会写，而是知道这种“最简单”的题，往往最能暴露一个人写代码的习惯。你是在方法里直接System.out.println，还是把逻辑拆成独立方法？你知不知道只需要判断到根号n就能结束？你能不能解释清埃拉托斯特尼筛选法的原理？这三种写法对应的复杂度差别有多大？那次面试从这道题引出，聊了差不多半小时，从试除法聊到Miller-Rabin，从稳定性排序聊到HashMap的扩容机制。后来我拿到了offer，私下复盘时发现，真正让我加分的不是背了多少八股文，而是我能把一道“小学生题”讲出层次。
也正是从那次之后，我开始认真整理Java基础题背后的算法与工程思维。这篇文章我打算以“求100以内素数”为入口，把暴力解法、优化解法、筛选法全部写一遍，每一步都配上代码、复杂度分析、易错提醒，最后再聊聊这道题在Java面试和工程里还能怎么延伸。文章面向的是：准备Java面试的求职者、刚入门Java想打牢基础的新手，以及想在公司内部做技术分享的开发者。读完之后，你不只是会“背出”一个答案，而是能真正理解这道题背后的算法演进逻辑，并在面试中举一反三。
2. 需求拆解与算法选型：从“能跑”到“高效”的三级递进
2.1 先搞清楚什么是素数，边界条件有哪些
素数也叫质数，定义是：大于1的自然数中，除了1和它本身以外不再有其他因数的数。这里有两个关键点：第一，1不是素数，这是最经典的边界条件，很多人一上来就把1算进去了；第二，2是最小的素数，也是唯一的偶素数，这个特性在后面做优化时非常有用。
判断一个数n是否为素数，最朴素的做法是：从2开始，一直试除到n-1，如果之间没有任何一个数能整除n，则n是素数。这个定义式的思路完全正确，但效率极低。假设要判断100以内所有素数，每个数都要从头试除到尾，总共大约要做1+2+3+...+99次取模运算，虽然现代计算机算这个毫无压力，但一旦把“100”换成“100万”“1亿”，这种写法就会直接卡死。
所以在动手写代码前，我习惯先把需求量化：输入n，找出[2, n]区间内所有素数。这里的n是100，产出应该是一个列表：[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]，一共25个。这个结果本身就是天然的测试用例，写完代码后第一时间跑一遍，比对个数和数值，能快速验证正确性。
2.2 暴力试除法：最容易想到，但性能最差
暴力试除法的Java实现大概是这样的：
public static boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { for (int i = 2; i <= 100; i++) { if (isPrime(i)) { System.out.print(i + " "); } } }这个写法逻辑清晰，性能也没问题，因为100这个数据量实在太小了。但如果你在面试中只写出这一版，面试官大概率会追问一句：“还能怎么优化？”这时候如果你卡住了，说明你对算法的理解还停留在“代码能跑”的层面。
我个人的习惯是，凡是涉及“判断素数”的场景，都默认用“试除到根号n”的版本，原因很简单：如果n有一个大于根号n的因数a，那么必然存在一个小于根号n的因数b = n/a，也就是说，只要在2到根号n之间找不到因数，后面也一定找不到。这个数学推理非常朴素，却是素数判断优化的第一块基石。
2.3 筛选法思维：用空间换时间，一网打尽所有素数
当题目从“判断单个素数”变成“求区间内所有素数”，有经验的开发者会立刻想到另一种完全不同思路——埃拉托斯特尼筛选法（Sieve of Eratosthenes）。这个方法的核心思想不是去“试除”，而是“标记”：先假设2到n之间所有数都是素数，然后从2开始，把2的倍数全部标记为合数；接着找到下一个未被标记的数3，把3的倍数全部标记为合数；再下一个是5，因为4已经被2的倍数标记过了，以此类推。最后，所有未被标记的数就是素数。
我第一次接触这个算法时，觉得它特别像一个生活场景：一个班50个人，老师说要找出所有“没被点名过”的同学。她从2号开始喊：“2号举手，所有2的倍数都坐下。”再喊3号：“3号举手，所有3的倍数都坐下。”等全部喊完，还站着的就是没被任何数整除过的素数。这个过程可以用布尔数组轻松模拟，时间复杂度为O(n log log n)，空间复杂度O(n)。
对于求100以内素数这种小任务，筛选法看起来有点“大炮打蚊子”，但它却是后续处理更大规模素数问题（比如求100万以内素数个数）的标准解法。更重要的是，通过这三种方案（暴力、根号优化、筛选法）的对比，你能在面试中展示出完整的思维链条：从“能跑”→ 正确性优化 → 性能优化 → 空间换时间。这个演进过程，恰好是面试官最喜欢的考察路径。
3. 三种核心方案的Java实现与逐行解读
3.1 方案一：朴素试除法，完整代码与易错点
先给出方案一的完整代码，并补充几个小的健壮性改进：
public class PrimeFinder { public static boolean isPrime(int n) { if (n <= 1) { return false; } for (int i = 2; i < n; i++) { if (n % i == 0) { return false; } } return true; } public static void main(String[] args) { List<Integer> primes = new ArrayList<>(); for (int i = 2; i <= 100; i++) { if (isPrime(i)) { primes.add(i); } } System.out.println("100以内的素数：" + primes); System.out.println("素数个数：" + primes.size()); } }这里我用了ArrayList来收集结果，而不是直接打印，是为了后续能对结果做进一步处理，比如统计个数、接续计算求和。直接打印看起来很直接，但在真实项目中，逻辑和方法边界往往不会这么简单，分离“计算”和“输出”是好习惯。
这段代码有几个易错点值得单独提一下：
第一个易错点是边界条件漏判。不少人写isPrime时只判断n == 1，忘记了n <= 1这个统一判断。如果输入是0或者负数，0 % 2 == 0会返回false，负数的情况则可能直接进入循环，结果不可预期。严格来讲，素数的定义域是“大于1的自然数”，所以入口处直接if (n <= 1) return false，一句话挡掉所有非法输入。
第二个易错点是循环起始值写错。有人写成for (int i = 1; i < n; i++)，那n % 1永远等于0，所有数都会被判成合数。看起来是低级错误，但在紧张的面试手写代码环节，这种低级错误很容易发生。我的建议是手写代码时先在草稿纸上标注“循环从2开始，到n结束，不包含n本身”，再落笔到白板上。
第三个易错点是返回值位置。return true如果写在for循环内部，那么当i=2时，如果n % 2 != 0就会马上返回true，根本没判断后面的因数，这是逻辑上最隐蔽的错。正确写法是：循环内但凡找到一个能整除的因数就return false，循环结束后再return true，二者顺序不能反。
3.2 方案二：根号优化，数学原理与边界推导
方案二的核心改动只有一个地方：把循环条件从i < n改成i <= Math.sqrt(n)。这里有一个细节，为什么是<=而不是<？因为假如n恰好是一个完全平方数，比如49，它的因数之一是7，而7刚好等于根号49。如果用i < Math.sqrt(n)，那么i最大只到6，7这个因数不会被检查到，49就会被误判为素数。这种边界在面试中极易被忽略，属于“低概率高后果”的典型坑。
代码实现如下：
public static boolean isPrimeOptimized(int n) { if (n <= 1) { return false; } if (n == 2) { return true; } if (n % 2 == 0) { return false; } int sqrt = (int) Math.sqrt(n); for (int i = 3; i <= sqrt; i += 2) { if (n % i == 0) { return false; } } return true; }我在这里额外做了两件事：单独判断2，然后偶数一律返回false，循环从3开始步长为2。这背后的逻辑是：除了2以外，所有偶数都不可能是素数，因此主循环只需要考察奇数。这个“跳过已知不可能”的思路，在算法设计中叫剪枝，虽然在这里收益不大，但它展示了一种意识：在动手循环之前，先把明显不满足条件的候选者排除掉。
想象一下，你去参加一个选秀节目，评委说要先看所有选手的表演。但节目组已经知道“身高不足1米2的选手不能通过初筛”，于是直接把这些选手筛掉，只让剩下的选手上台。程序里的提前判断就是节目组的初筛，虽然看起来只是省了几个循环，但当你处理的数从100变成10亿时，少做5亿次取模运算，差距就是毫秒级和分钟级的区别。
3.3 方案三：埃拉托斯特尼筛选法，空间换时间的典范
筛选法的代码和前面两种完全不同，它需要额外申请一个布尔数组来记录每个数是否为素数。初始时默认所有数都是素数，然后从2开始，把每个素数的倍数全部标记为合数。这里有一个经典优化：内层循环的起始位置是i * i而不是i * 2。为什么？因为i的较小倍数（比如2i、3i、...、(i-1)i）已经在之前处理更小的素数时被标记过了。比如i=7时，72、73、74、75、7*6这些数，分别会被2、3、2、5、2的循环覆盖，再标记一遍纯属浪费。
public static List<Integer> sieveOfEratosthenes(int n) { boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); List<Integer> result = new ArrayList<>(); for (int i = 2; i <= n; i++) { if (isPrime[i]) { result.add(i); // 如果 i*i 溢出 int 范围，需转 long 判断 if ((long) i * i <= n) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } } return result; }需要注意几个细节：
数组大小是n+1，因为下标从0开始，我们需要能访问到isPrime[100]。Java中数组声明后，boolean元素默认值是false，所以必须用Arrays.fill(isPrime, true)把所有位置先置为true，就是先假设所有人都是素数。下标0和1没有实际含义，即使它们被置为true，也不会被i从2开始的循环触及，不会影响结果。
内层循环从ii开始，但j的类型是int，当n很大时，ii可能超出int的表示范围。在100这个范围内完全不用考虑，但写通用工具类时这是一个必须防的坑。我通常会在外层循环里判断(long) i * i <= n，先把乘法转成long再做比较，确保安全。
每次找到一个新的素数i，就把它的倍数全部标记为false。这个过程反复进行，直到遍历完整个数组。最后result列表里装的就是从小到大排列的素数。
为了直观验证，你可以跑一下这个main方法：
public static void main(String[] args) { List<Integer> primes = sieveOfEratosthenes(100); System.out.println(primes); System.out.println(primes.size()); }输出结果：从2开始一直到97，共25个数字。和暴力法的结果完全一致。这也是一个很好的测试思路：用两种不同算法互相验证，比单独跑一种更有说服力。
4. 复杂度对比与测试验证：选型不能靠感觉
4.1 三种方案的时间复杂度、空间复杂度对比
口说无凭，我整理了一张表，把你以后可能遇到的面试追问一次性说清楚：
| 方案 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力试除法 | O(n√n)（实际是O(n^2)，如果每个数都试除到自身） | O(1) | 数据量极小，追求代码最简单 |
| 根号优化试除法 | O(n√n)（每个数判断到根号n） | O(1) | 单个判断，或n在10^5以下 |
| 埃拉托斯特尼筛选法 | O(n log log n) | O(n) | 区间查询、大量素数一次性求出 |
这里要特别解释一下为什么暴力法写成O(n^2)，根号优化写成O(n√n)。判断某个单个数n，暴力试除需要n-2次取模，判断2到n所有数，总共要执行约2+3+...+n次，数量级是O(n^2)。根号优化后，判断每个数只需要√n次取模，总数量级O(n√n)。筛选法最神奇，每个合数会被标记多次，但标记的总次数大约是n/2 + n/3 + n/5 + ...，这个调和级数的和收敛到n log log n，所以总复杂度是O(n log log n)。
我常在面试辅导中让候选人模拟跑一下这三个算法：n=10万时，暴力法可能要几秒，根号优化瞬间就出结果，筛选法也是毫秒级。但当n来到1亿时，根号优化会非常吃力，筛选法虽然要开1亿的布尔数组（约100MB内存），却能在若干秒内完成。所以选哪个方案，完全取决于你的数据规模和对内存的容忍度。
4.2 用JUnit和结果清单验证正确性
无论用哪种算法，最终必须回答一个问题：结果对不对？我建议把所有结果收集到List里，然后用JUnit写一个简单的断言测试，比如：
@Test public void testPrimeUnder100() { List<Integer> expected = Arrays.asList(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); List<Integer> actual = PrimeFinder.sieveOfEratosthenes(100); assertEquals(expected, actual); }测试一旦通过，三种方案输出一致，基本可以确定算法逻辑没有大问题。我自己在开发中写算法工具类时，都会保留这样的“黄金用例”，以后代码重构、换写法时，跑一遍测试就能防止回归问题。这也是一个很好的工程习惯：哪怕是20行的小算法，也值得有自动化测试保护。
4.3 实测：把n放大，看三种方案的真实耗时差异
为了让你更直观感受复杂度差异，我写了一个简单的基准测试：
public static void main(String[] args) { int n = 1000000; long start = System.currentTimeMillis(); List<Integer> primes = sieveOfEratosthenes(n); long end = System.currentTimeMillis(); System.out.println("100万以内素数个数: " + primes.size() + ", 耗时: " + (end - start) + "ms"); }在一台普通笔记本上，筛选法跑100万以内素数通常只需要几十毫秒。如果用根号优化法，大约需要几百毫秒到一秒不等。如果用最暴力的O(n²)写法，可能几十秒都跑不完。这个实验结果足够说明：在“求区间内所有素数”这种批量场景下，筛选法就是碾压级别的存在。但如果是“判断单个数是否为素数”，筛选法反而需要预先生成所有小于该数的素数表，内存和初始化成本都高，这时候直接上根号优化法更合适。选型永远是基于场景的，不存在绝对最优的方案。
5. 从100延展到更大规模：算法升级与工程应用场景
5.1 当n变成10^6、10^7，需要注意哪些问题
如果面试官在原题基础上加了一个条件：求100万以内素数的个数，那么你应该立刻联想到数论中的素数计数函数π(n)。这也是热搜词里“论小于给定数值的素数个数”所指的方向。直接用筛选法生成100万以内的素数，然后统计个数，当然可以。但如果你需要反复查询不同区间的素数个数，每次都重新生成一遍显然不划算。业界更高级的做法是：一次预处理，把前缀素数个数数组算出来，之后每次查询只用O(1)时间返回结果。
在Java里可以这样设计：先用筛选法找出所有素数，然后构建一个prefix数组，prefix[i]表示[2, i]范围内素数的个数。查询[a, b]区间的素数个数时，直接返回prefix[b] - prefix[a - 1]。这个思路其实和前缀和算法一脉相承，也是面试中很常见的引申考点。
当n来到10^7以上，布尔数组的内存开销开始变得明显。Java中boolean数组每个元素占1个字节，开一个长度10^7的数组需要10MB，还能接受；但到10^9就是1GB，基本不可行。这时候有两个优化方向：一是用BitSet来压缩存储，每个数只占1位，内存直接缩小8倍；二是分段筛选，把区间切成多段，逐段处理，避免一次性申请超大数组。后者在分布式的MapReduce框架里有很经典的应用：每个节点负责一段区间，最后汇总结果。
5.2 素数在RSA加密、哈希函数、随机数生成中的工程角色
你以为素数只是面试题里的玩具？工程应用中它无处不在。最典型的场景是RSA非对称加密算法，它的安全性建立在“大素数相乘容易，但分解大合数极其困难”这一数学事实上。生成RSA密钥对时，第一步就是生成两个随机的大素数p和q（通常都有几百位十进制），然后计算n = p * q。这里的“判断一个几百位的大数是否为素数”，就不能再靠试除法了，而是要用Miller-Rabin素性测试——一种基于费马小定理的随机化算法，能在极短时间内以极高概率判定一个数是否为素数。
另一个场景是哈希表的容量设置。很多实现会倾向于把哈希桶数设成素数，原因与数学上的取模均匀性有关：如果容量是合数，且哈希值的分布规律与容量的因子有冲突，则可能出现严重的哈希碰撞。Java的HashMap在扩容时使用2的幂次，是为了优化位运算，但不少其他语言或自研哈希表确实会故意选用素数作为槽位数。
再举个例子，很多在线游戏需要生成随机事件，比如“这次开宝箱有1%的概率出稀有道具”。底层可能用到线性同余生成器，也可以通过素数模数来增强随机周期。一个素数模数可以让伪随机序列的周期更长、分布更均匀。虽然现代Java更推荐使用ThreadLocalRandom或SecureRandom，但理解其中的素数原理，能让你在设计系统时多一个思考维度。
5.3 进阶话题：费马小定理与Miller-Rabin素性测试
既然聊到了RSA，我就顺带把Miller-Rabin的原理大概讲一讲，毕竟这也是Java面试八股文里常见的高级考点。
费马小定理说的是：如果p是素数，a是任意不是p的倍数的整数，那么a^(p-1) ≡ 1 (mod p)。反过来，如果某个数n满足对某个a有a^(n-1) ≡ 1 (mod n)，是否就能说明n是素数？很遗憾，不能。有些合数（比如卡迈克尔数）对几乎所有a都满足这个同余式，它们能骗过朴素的费马测试。Miller-Rabin的改进在于：把n-1分解成d * 2^s的形式，然后检查一系列条件，合数要同时满足这些条件是非常困难的，所以通过多次随机选取不同的a，就能把误判概率压到极低。
在实际的Java开发中，JDK本身就提供了BigInteger.isProbablePrime(int certainty)方法，certance参数代表你愿意承担的出错概率，传入100或以上基本可以认为是安全的。我在做需要生成大素数的工具类时，底层调用的就是它。这也是为什么JDK能让普通开发者不必了解数论细节，也能完成安全相关的开发。
6. 面试场景复盘：一道素数题的八股文延伸与实战应答
6.1 常见面试追问，以及答题思路拆解
面试官问完“求100以内素数”后，通常不会就此打住，而是一层层往下挖。我把最常见的追问整理成了一份“问答速查表”，你可以对着自查：
| 面试官追问 | 考察点 | 建议应答思路 |
|---|---|---|
| 为什么只需要判断到根号n？ | 数学基础，因数对称性 | 用a*b=n，a和b不能同时大于根号n来解释 |
| 筛选法为什么从ii而不是i2开始？ | 对算法执行过程的理解 | 比i小的倍数已被更小的素数标记过，重复标记无意义 |
| 布尔数组初始为什么是true？ | Java数组默认值 | 能用一句话说清，但很多人会忽略 |
| 2是素数吗？1呢？ | 边界条件意识 | 2是唯一偶素数，1不是素数 |
| 时间复杂度是多少？还能优化吗？ | 算法复杂度分析能力 | 暴力O(n²)、根号O(n√n)、筛选O(n log log n)，大数用Miller-Rabin |
| 如果求100万以内素数个数呢？ | 能否把算法推广 | 筛选法 + 前缀和，一次性预处理，O(1)查询 |
面对这些追问，有一个通用话术：“我第一版会先用最直观的试除法保证正确性，然后根据数据规模引入根号优化，如果批量查询素数个数，我会改用筛法并配合前缀和。”这个“由正确到高效、由单点到批量”的表达框架，在面试中比死记硬背一个答案有效得多。
6.2 动态规划、线程等待与这道题的“隐性关联”
热搜词里出现了“java线程等待都完成”、“java动态代理”，看起来和素数无关，但在实际面试中，题目往往会和并发、“设计模式”做结合。举个例子，面试官可能会让你用多线程去计算100万以内素数个数，你会怎么做？一种思路是：把[2, 100万]分成多个区间，每个线程负责一个区间，用根号优化法分别统计，最后汇总。这时候，如何等待所有线程都完成？就需要用到ExecutorService的invokeAll、CountDownLatch或者CompletableFuture.allOf。素数题就变成了多线程协作题。
另一种更“卷”的做法是并发筛法：在主线程做好标记数组后，用线程池并行标记每个合数段。但对100万这种规模，并发反而可能因为锁竞争而变慢。面试考这个，本质是看你能否“设计出正确且能落地的并发方案”，而不是真的要求性能飞跃。
类似地，素数题还可以和缓存设计结合：比如把[2, 10^6]以内的素数表做成一个单例缓存，供所有请求复用。Spring容器里可以把素数表放进一个@PostConstruct初始化的Bean，或者用双重检查锁单例。这样一来，一道“基础题”就自然延伸到了单例模式、并发安全、缓存设计等话题——这些全都是Java核心技术。
6.3 从手写代码到工程规范：变量命名、方法拆分、测试覆盖
最后一个想强调的点，是代码风格。求100以内素数，十行代码能写完，但“能写完”和“写得好”是两码事。我见过不少候选人在白板上写出类似is?、f1、temp这种命名，也见过把判断逻辑全部塞进main方法里。这不一定导致错误，但给面试官的印象会差很多。
我的建议是：
- 方法名用isPrime(int n)、sieveOfEratosthenes(int n)这种见名知意的风格，符合Java命名规范。
- 一个方法只做一件事。isPrime只负责判断单个数字，sieve只负责生成素数列表，打印逻辑交给调用方。
- 用List 而不是int[]作为返回值，避免固定长度限制，也更符合日常编程习惯。
- 至少覆盖三种边界测试用例：n=2时返回[2]；n=1时返回空列表；n=0或负数时返回空列表，而不是抛异常或死循环。
这些习惯看起来琐碎，但它们恰恰是区分“刷题党”和“靠谱工程师”的分水岭。面试官一天面很多人，代码风格优秀的候选人往往能留下更深的印象。
个人实操心得总结
题目写到这里，我想聊聊自己这几年写Java的感受。
如果你只是打算应付一面，背下筛选法代码就够了，但想在这条路上走远，最好的方式是“把每道基础题都当成一颗种子”。一颗素数题的种子可以长成算法复杂度、数论、加密学、并发编程、设计模式一整片树林。我在实际开发中确实写过一次素数相关工具类，当时是为了做一个数据脱敏模块，需要用大素数生成随机偏移量——因为项目用了Spring Boot，我对素数表的初始化做了懒加载，并配了ConcurrentHashMap做缓存，保证高并发下不会重复计算。写完那几十行代码后，我重新理解了为什么面试官那么喜欢问素数：它足够小，小到可以用五分钟讲完；又足够大，大到能装下计算机科学的半壁江山。
最后再分享一个小技巧。如果你在做这道题的时候，发现某个优化思路一时想不通，不用硬记。你可以在草稿纸上把数字写出来，比如列出1到30，用笔把2的倍数划掉，再把3的倍数划掉，然后观察剩下哪些数。这个过程只需要两分钟，但它建立的“筛子”感，比死记十行代码牢固得多。很多算法都是从这种“手算体验”里生长出来的，Java只是把它们表达了出来。希望你也能在写代码之外，保留一点对数学直觉的敏感。
