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以内所有素数每个数都要从头试除到尾总共大约要做123...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) { ListInteger 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循环内部那么当i2时如果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最大只到67这个因数不会被检查到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已经在之前处理更小的素数时被标记过了。比如i7时72、73、74、75、7*6这些数分别会被2、3、2、5、2的循环覆盖再标记一遍纯属浪费。public static ListInteger sieveOfEratosthenes(int n) { boolean[] isPrime new boolean[n 1]; Arrays.fill(isPrime, true); ListInteger 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; }需要注意几个细节数组大小是n1因为下标从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) { ListInteger 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)每个数判断到根号nO(1)单个判断或n在10^5以下埃拉托斯特尼筛选法O(n log log n)O(n)区间查询、大量素数一次性求出这里要特别解释一下为什么暴力法写成O(n^2)根号优化写成O(n√n)。判断某个单个数n暴力试除需要n-2次取模判断2到n所有数总共要执行约23...n次数量级是O(n^2)。根号优化后判断每个数只需要√n次取模总数量级O(n√n)。筛选法最神奇每个合数会被标记多次但标记的总次数大约是n/2 n/3 n/5 ...这个调和级数的和收敛到n log log n所以总复杂度是O(n log log n)。我常在面试辅导中让候选人模拟跑一下这三个算法n10万时暴力法可能要几秒根号优化瞬间就出结果筛选法也是毫秒级。但当n来到1亿时根号优化会非常吃力筛选法虽然要开1亿的布尔数组约100MB内存却能在若干秒内完成。所以选哪个方案完全取决于你的数据规模和对内存的容忍度。4.2 用JUnit和结果清单验证正确性无论用哪种算法最终必须回答一个问题结果对不对我建议把所有结果收集到List里然后用JUnit写一个简单的断言测试比如Test public void testPrimeUnder100() { ListInteger 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); ListInteger actual PrimeFinder.sieveOfEratosthenes(100); assertEquals(expected, actual); }测试一旦通过三种方案输出一致基本可以确定算法逻辑没有大问题。我自己在开发中写算法工具类时都会保留这样的“黄金用例”以后代码重构、换写法时跑一遍测试就能防止回归问题。这也是一个很好的工程习惯哪怕是20行的小算法也值得有自动化测试保护。4.3 实测把n放大看三种方案的真实耗时差异为了让你更直观感受复杂度差异我写了一个简单的基准测试public static void main(String[] args) { int n 1000000; long start System.currentTimeMillis(); ListInteger 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*bna和b不能同时大于根号n来解释筛选法为什么从ii而不是i2开始对算法执行过程的理解比i小的倍数已被更小的素数标记过重复标记无意义布尔数组初始为什么是trueJava数组默认值能用一句话说清但很多人会忽略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[]作为返回值避免固定长度限制也更符合日常编程习惯。至少覆盖三种边界测试用例n2时返回[2]n1时返回空列表n0或负数时返回空列表而不是抛异常或死循环。这些习惯看起来琐碎但它们恰恰是区分“刷题党”和“靠谱工程师”的分水岭。面试官一天面很多人代码风格优秀的候选人往往能留下更深的印象。个人实操心得总结题目写到这里我想聊聊自己这几年写Java的感受。如果你只是打算应付一面背下筛选法代码就够了但想在这条路上走远最好的方式是“把每道基础题都当成一颗种子”。一颗素数题的种子可以长成算法复杂度、数论、加密学、并发编程、设计模式一整片树林。我在实际开发中确实写过一次素数相关工具类当时是为了做一个数据脱敏模块需要用大素数生成随机偏移量——因为项目用了Spring Boot我对素数表的初始化做了懒加载并配了ConcurrentHashMap做缓存保证高并发下不会重复计算。写完那几十行代码后我重新理解了为什么面试官那么喜欢问素数它足够小小到可以用五分钟讲完又足够大大到能装下计算机科学的半壁江山。最后再分享一个小技巧。如果你在做这道题的时候发现某个优化思路一时想不通不用硬记。你可以在草稿纸上把数字写出来比如列出1到30用笔把2的倍数划掉再把3的倍数划掉然后观察剩下哪些数。这个过程只需要两分钟但它建立的“筛子”感比死记十行代码牢固得多。很多算法都是从这种“手算体验”里生长出来的Java只是把它们表达了出来。希望你也能在写代码之外保留一点对数学直觉的敏感。
Java求100以内素数：从暴力试除到埃拉托斯特尼筛选法的算法演进与面试要点
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以内所有素数每个数都要从头试除到尾总共大约要做123...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) { ListInteger 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循环内部那么当i2时如果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最大只到67这个因数不会被检查到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已经在之前处理更小的素数时被标记过了。比如i7时72、73、74、75、7*6这些数分别会被2、3、2、5、2的循环覆盖再标记一遍纯属浪费。public static ListInteger sieveOfEratosthenes(int n) { boolean[] isPrime new boolean[n 1]; Arrays.fill(isPrime, true); ListInteger 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; }需要注意几个细节数组大小是n1因为下标从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) { ListInteger 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)每个数判断到根号nO(1)单个判断或n在10^5以下埃拉托斯特尼筛选法O(n log log n)O(n)区间查询、大量素数一次性求出这里要特别解释一下为什么暴力法写成O(n^2)根号优化写成O(n√n)。判断某个单个数n暴力试除需要n-2次取模判断2到n所有数总共要执行约23...n次数量级是O(n^2)。根号优化后判断每个数只需要√n次取模总数量级O(n√n)。筛选法最神奇每个合数会被标记多次但标记的总次数大约是n/2 n/3 n/5 ...这个调和级数的和收敛到n log log n所以总复杂度是O(n log log n)。我常在面试辅导中让候选人模拟跑一下这三个算法n10万时暴力法可能要几秒根号优化瞬间就出结果筛选法也是毫秒级。但当n来到1亿时根号优化会非常吃力筛选法虽然要开1亿的布尔数组约100MB内存却能在若干秒内完成。所以选哪个方案完全取决于你的数据规模和对内存的容忍度。4.2 用JUnit和结果清单验证正确性无论用哪种算法最终必须回答一个问题结果对不对我建议把所有结果收集到List里然后用JUnit写一个简单的断言测试比如Test public void testPrimeUnder100() { ListInteger 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); ListInteger actual PrimeFinder.sieveOfEratosthenes(100); assertEquals(expected, actual); }测试一旦通过三种方案输出一致基本可以确定算法逻辑没有大问题。我自己在开发中写算法工具类时都会保留这样的“黄金用例”以后代码重构、换写法时跑一遍测试就能防止回归问题。这也是一个很好的工程习惯哪怕是20行的小算法也值得有自动化测试保护。4.3 实测把n放大看三种方案的真实耗时差异为了让你更直观感受复杂度差异我写了一个简单的基准测试public static void main(String[] args) { int n 1000000; long start System.currentTimeMillis(); ListInteger 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*bna和b不能同时大于根号n来解释筛选法为什么从ii而不是i2开始对算法执行过程的理解比i小的倍数已被更小的素数标记过重复标记无意义布尔数组初始为什么是trueJava数组默认值能用一句话说清但很多人会忽略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[]作为返回值避免固定长度限制也更符合日常编程习惯。至少覆盖三种边界测试用例n2时返回[2]n1时返回空列表n0或负数时返回空列表而不是抛异常或死循环。这些习惯看起来琐碎但它们恰恰是区分“刷题党”和“靠谱工程师”的分水岭。面试官一天面很多人代码风格优秀的候选人往往能留下更深的印象。个人实操心得总结题目写到这里我想聊聊自己这几年写Java的感受。如果你只是打算应付一面背下筛选法代码就够了但想在这条路上走远最好的方式是“把每道基础题都当成一颗种子”。一颗素数题的种子可以长成算法复杂度、数论、加密学、并发编程、设计模式一整片树林。我在实际开发中确实写过一次素数相关工具类当时是为了做一个数据脱敏模块需要用大素数生成随机偏移量——因为项目用了Spring Boot我对素数表的初始化做了懒加载并配了ConcurrentHashMap做缓存保证高并发下不会重复计算。写完那几十行代码后我重新理解了为什么面试官那么喜欢问素数它足够小小到可以用五分钟讲完又足够大大到能装下计算机科学的半壁江山。最后再分享一个小技巧。如果你在做这道题的时候发现某个优化思路一时想不通不用硬记。你可以在草稿纸上把数字写出来比如列出1到30用笔把2的倍数划掉再把3的倍数划掉然后观察剩下哪些数。这个过程只需要两分钟但它建立的“筛子”感比死记十行代码牢固得多。很多算法都是从这种“手算体验”里生长出来的Java只是把它们表达了出来。希望你也能在写代码之外保留一点对数学直觉的敏感。
