很多初学者在学Java循环和数组的时候都会碰到一道题找出某个范围内的所有素数然后存进数组返回。这题看着简单其实里面藏了不少值得掰扯的东西——既有算法层面的效率问题又有Java数组操作层面的细节。你去看各大公司笔试和面试题库这道题从入门版到优化版都有所以它才被翻来覆去地考。我从自己实际写过、也帮别人改过代码的经验出发把这题一次性讲透。从最基础的素数判断原理开始到你该怎么设计方法签名、怎么写循环、怎么处理动态长度数组、以及到后面怎么引入筛法做性能优化全部覆盖到。最后再聊几个我在实际编码和面试代码审查里经常遇到的坑帮你提前避开。1. 先搞清楚需求这个“指定范围”到底该怎么拆1.1 你以为的“查找素数”其实是在考察三件事先说个比较反直觉的事情这道题表面上考的是“你怎么判断一个数是不是素数”但实际上考官真正想看的远不止这个。拆开“Java中高效查找指定范围内素数并返回数组”这个需求至少包含三层要求——第一层是核心算法也就是判断一个数字是否为素数的基础能力第二层是区间遍历策略你是在每一个数字上都从头做一次判断还是利用某种规律跳过大量无效数字第三层是Java集合与数组之间的转换能力因为你有“返回数组”这么个硬性要求而Java里数组长度又是固定的怎么在不知道最终结果数量的情况下填满数组这个处理方式能直接看出你的基本功。换句话说考核点覆盖了“算法思维Java基础语法数据结构运用”三个维度。这就是为什么我在带实习生的时候特别爱出这道题——只要看一个人怎么设计方法签名、怎么处理长度为0的边界情况、怎么写循环结束条件大概就能判断出他有没有系统性地写过代码。1.2 方法签名设计先想清楚输入输出再动手我见过太多人拿到题目直接开写写完才发现不知道该传什么参数、返回值怎么处理。所以我建议你拿到任何编程题的时候第一件事不是写代码而是把方法签名写出来。就这道题而言最自然的方式是public static int[] findPrimes(int start, int end)这里有几个点需要确认传入的 start 和 end 是闭区间还是左闭右开范围需不需要包含负数end 小于 start 的时候是返回空数组还是抛异常这些都是需求分析的一部分。我在实际编码中通常约定[left, right]闭区间并且要求right不小于2因为2是最小的素数小于2的范围内不可能有素数到时候直接返回空数组即可。方法签名设计的核心思想其实就是一句话让调用方用起来不会产生歧义让实现方写起来不用到处打补丁。2. 基础实现从零开始判断一个数是否为素数2.1 素数的定义与试除法的核心逻辑素数也叫质数指的是在大于1的自然数中除了1和它本身以外不再有其他因数的数。2是最小的素数同时也是唯一一个偶素数——就这一个特性后面会给我们带来一个极大的性能优化点。判断一个数 n 是否为素数最朴素的思想叫“试除法”拿从2开始一直到 n-1 的所有整数去除n如果任何一个能整除说明 n 是合数如果全都不能整除说明 n 是素数。这个逻辑用代码写出来是这样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; }逻辑没有问题但效率非常差。如果你拿这个版本去算100万以内的素数循环次数会膨胀到难以接受的程度。问题出在“从2一直除到n-1”这段——绝大多数试除都是白费的例如判断101是不是素数你根本不需要去试除100试到10就够了。2.2 为什么只需要检查到平方根证明与实验这里有一个非常经典的数学结论如果 n 是合数那么它一定有一个不大于√n的因子。假设 n a×b如果a和b都大于√n那么a×b就会大于n这显然是矛盾的。所以至少有一个因子小于等于√n。这个结论意味着什么呢意味着我们在试除的时候根本不需要循环到n-1只需要循环到√n就够了。如果到√n为止都找不到能整除n的数后面也不可能找到了。代码改成这样public static boolean isPrime(int n) { if (n 2) { return false; } // i * i n 等价于 i Math.sqrt(n) for (int i 2; i * i n; i) { if (n % i 0) { return false; } } return true; }注意一个细节我在这里用的是i * i n而不是i Math.sqrt(n)。为什么因为Math.sqrt涉及到浮点运算每一次循环都要计算一次开方性能损耗不小而i * i只是整数乘法速度要快得多。当然用int的时候要注意i*i可能会溢出——不过在素数判断这个场景里i最多到46340左右远不会溢出所以是安全的。我自己实测过判断100万以内的全部素数用“i n”版本大概要耗时几十秒而优化到“i * i n”版本只需要几百毫秒差距达到几十倍。仅仅一个循环边界的改动性能天差地别这就是算法优化的魅力。3. 范围扫描与数组构建把素数逐个收进数组3.1 初步方案集合过渡后再转数组现在有了单个数判断的能力下一步就是在指定范围内逐个扫描把素数收集起来。写代码之前先想清楚一个让人头疼的问题素数在指定范围内的个数未知而Java数组一创建长度就固定了。比如你要找100到200之间的素数你不先数一遍根本不知道有几个那数组该开多长呢解决方案有几个。第一个方案是先用ArrayList存最后再转成数组import java.util.ArrayList; import java.util.List; public static int[] findPrimes(int start, int end) { ListInteger primes new ArrayList(); for (int n start; n end; n) { if (isPrime(n)) { primes.add(n); } } int[] result new int[primes.size()]; for (int i 0; i primes.size(); i) { result[i] primes.get(i); } return result; }这个方案很直观也是绝大多数人会写的写法。先把符合条件的元素放进一个可以动态扩容的容器里最后再转成定长数组。3.2 进一步优化两遍扫描或者用流式处理集合过渡的方案虽然直观但存在两个小问题——一是需要额外引入ArrayList对象会创建很多Integer包装对象二是add过程中ArrayList还会多次扩容产生不必要的数组拷贝。如果你追求更极致的效率可以考虑“两遍扫描”方案第一遍先遍历区间只计数不存储第二遍再遍历一次区间这次把素数填进已经确定长度的数组里。public static int[] findPrimes(int start, int end) { // 第一遍扫描统计素数个数 int count 0; for (int n start; n end; n) { if (isPrime(n)) { count; } } // 构建定长数组 int[] result new int[count]; // 第二遍扫描填充数组 int index 0; for (int n start; n end; n) { if (isPrime(n)) { result[index] n; } } return result; }前后循环了两次总的时间仍然是O(m×√n)级别的只是常数项翻倍了但省掉了ArrayList扩容和Integer装箱的开销。在这个场景里两遍扫描其实也不是最优选择因为两次调用isPrime重复计算了。如果不想用ArrayList又不想两遍扫描可以用Java 8的Stream。代码可以写得非常简洁public static int[] findPrimes(int start, int end) { return java.util.stream.IntStream.rangeClosed(start, end) .filter(JavaPrimeTest::isPrime) .toArray(); }Stream的toArray底层会帮你处理动态长度的问题源码里也是先收集再建数组本质上还是容器过渡的思路但代码短了不少。用在笔试答题或者内部工具类里完全没问题但如果你的目标是把底层逻辑讲清楚还是自己手动写一遍比较好不然面试官追问起来容易露馅。4. 进阶方案当范围变大时上埃拉托斯特尼筛法4.1 为什么逐个判断在大范围场景下会力不从心上面的方案用“逐个判断”的思路解决小范围没问题但如果把范围放大到十万、百万甚至千万级别逐个判断的性能就会成为瓶颈。原因很简单每次调用isPrime(n)都要做约√n次除法运算。统计整个区间[2, N]里的素数时总计算量大约是Σ√nn从2到N这个量级差不多是O(N^1.5)。当N等于100万时需要执行的试除操作约为10亿次无论怎么微调循环细节这个量级的运算在现代CPU上都已经能感觉到明显的卡顿。判断100万以内的全部素数逐个判断需要跑几百毫秒到1秒左右但下面要说的筛法只需要几毫秒。差距达到了几百倍。4.2 筛法核心思想不是“找”素数而是“筛掉”合数埃拉托斯特尼筛法Sieve of Eratosthenes的思路非常巧妙它不判断每个数是不是素数而是直接从2开始把每个素数的倍数都标记为合数。一轮操作之后没被标记为合数的那些数自然就是素数。打个比方你就明白了想象有一排从2开始编号的箱子每个箱子里都有一张写着“不确定”的小卡片。你从2号箱子开始既然它是素数那你就把4、6、8、10……这些2的倍数箱子里的卡片全都改成“合数”。然后走到3号箱子发现它还是“不确定”那它就是素数于是你把6、9、12、15……这些3的倍数全部标记为合数。你再走到4号箱子发现已经被标记成合数了直接跳过。这样一路走下来最终所有还保持“不确定”状态的箱子就是素数。在代码里实现这个逻辑需要一个布尔数组来充当标记。具体步骤如下public static int[] findPrimesBySieve(int n) { // 只统计 [2, n] 范围内的素数n 2 则返回空数组 if (n 2) { return new int[0]; } boolean[] isComposite new boolean[n 1]; // 注意 i * i n而不是 i n for (int i 2; i * i n; i) { if (!isComposite[i]) { // 从 i*i 开始标记而不是从 2*i 开始这又是一个关键优化 for (int j i * i; j n; j i) { isComposite[j] true; } } } // 统计个数 int count 0; for (int i 2; i n; i) { if (!isComposite[i]) { count; } } // 填充数组 int[] primes new int[count]; int index 0; for (int i 2; i n; i) { if (!isComposite[i]) { primes[index] i; } } return primes; }有个地方我要特别提醒内层循环从i * i开始而不是从2 * i开始。这是因为所有比i*i小的i的倍数比如2i、3i、4i……在更早的循环里已经被更小的素数标记过了。举个例子当i等于7时2×714这个数早就被素数2标记过了3×721早就被素数3标记过4×728等于2×14还是2的倍数5×735早被5标记过6×742是2和3的倍数。所以直接从49开始标记7的倍数可以避免大量重复操作。这个优化对算法性能影响极大。如果从2i开始标记每个合数可能会被多个素数重复标记好多次虽说不影响结果但浪费的循环次数会非常多。从i²开始每个合数只会被它最小的质因子标记一次或少数几次时间复杂度从O(n log log n)的优秀表现进一步降低了常数项。4.3 指定起止范围时筛法该怎么配合使用上面写的筛法是统计从2开始到n的所有素数。那如果题目要求的是“100到200之间的素数”这种带左边界的情况怎么用筛法方法很简单先用筛法生成[2, end]范围内的所有素数然后用二分查找或者遍历找到第一个大于等于start的素数所在位置从那里截取到end为止。数组截取可以借助Arrays.copyOfRange方法public static int[] findPrimesInRange(int start, int end) { if (end 2 || start end) { return new int[0]; } // 算出 [2, end] 范围内的全部素数 int[] allPrimes findPrimesBySieve(end); // 找到第一个大于等于 start 的元素下标 int beginIndex 0; while (beginIndex allPrimes.length allPrimes[beginIndex] start) { beginIndex; } // 复制 [start, end] 范围内的素数 return Arrays.copyOfRange(allPrimes, beginIndex, allPrimes.length); }这里起点start如果小于2只需要从第一个素数2开始即可因为小于2的数绝不可能是素数我们已经用end小于2的条件兜底了。有一说一如果只是查找一个小区间的素数筛法反而有点“大材小用”——为了找100到200之间的素数去算到200的完整筛子可能还不如直接逐个判断快。但当end很大且你需要“频繁查询”这个范围内的素数时筛法一次预处理、多次查询的优势就体现出来了。这也是我为什么建议把两种方法都掌握的原因面试时要能说出来各自的优缺点和适用场景才显得你真的理解了。5. 边界条件与高频坑位这些地方最容易丢分5.1 小于2的数字一个不小心就返回错误结果素数定义里有一条铁律1不是素数0和负数也不是素数。这是很多没写过素数判断的同学最容易栽的坑。如果你的代码长这样for (int i 2; i n; i) { if (n % i 0) return false; } return true;当你拿n1走一遍循环条件2 1不成立直接跳到return true——1被错误地当成素数返回了。所以不论你后面怎么写开头一定要加上if (n 2) return false;这道防线。顺带记一下一个常被搞混的点2是素数也是唯一一个偶数素数。这个特性很实用比如你可以在遍历范围时先单独处理2然后只遍历奇数直接省掉一半的判断量。后面我会给出一版优化代码把这个特性用上。5.2 数组越界reverse一下你的循环条件可能就从越界变成了死循环写筛法的时候最常见的问题出在数组下标越界。比如你创建了boolean[] isComposite new boolean[end 1]大小是end1那么合法下标范围是0到end。在标记线程的时候如果写成for (int j i * i; j end; j i)就会漏掉end本身——如果end恰好是合数它可能就不会被正确标记。同样经典的还有循环条件写成j end之后j不断增加导致下标越界的情况这在调试中非常坑。由于数组是随机访问而不是链表结构越界通常不会被立即感知有时候要等数据被破坏之后才暴露出问题。所以每次设计循环边界的时候花30秒把首尾值代进去走一遍确认不会越界、不会漏项。这个“干跑代码”的习惯能帮你省下一大堆调试时间。5.3 int溢出面试官最爱挖的隐藏陷阱当n特别大时i * i n这里的i * i可能会溢出。比如i等于50000时ii是25亿已经超出int能表示的最大值21亿多会发生溢出变成负数导致循环条件判断出错。但话又说回来如果n是int类型的最大值21亿左右那么所有小于它且能被int表示的i其平方最大也不会超出int上界太多。这里有一个精确的界限只要i不超过46340ii就不会溢出。如果你是判断int范围内的数而你需要搜索到√n ≈ 46340恰好不会溢出所以大多数情况下还算安全。但如果你在通用方法里使用long类型或者传入的是long类型的数据就需要格外小心。判断long值是否素数时i * i的溢出会非常隐蔽而且危险。建议保险起见用i n / i这个条件它等价于i * i n但完全不会溢出只是每次循环多一次除法运算。在性能要求不那么极端的场景里用这个写法更稳。5.4 返回空数组还是null一个影响整个调用链的设计决策方法返回类型是数组那当范围内没有任何素数时应该返回什么我见过有人return null也见过有人直接抛异常。从工程实践的角度讲这两种做法都会给调用方带来麻烦——调用方如果没做null判断直接遍历返回值就会抛出空指针异常。我强烈建议你返回长度为0的空数组new int[0]。Java里数组长度可以为0遍历它不会出错调用方不需要写任何特殊的防御代码。这也符合“返回空集合而不是null”这条经典的设计原则面试时你能主动提到这一点会是加分项。6. 完整示例代码把边界处理与性能优化都揉在一起前面把几种方案和坑都说完了现在我给你一个可以直接使用的高效完整示例代码。它会把上面聊到的几个关键点全都能体现出来import java.util.Arrays; public class PrimeFinder { private PrimeFinder() { // 工具类不提供实例化入口 } public static int[] findPrimes(int start, int end) { // 范围无交集或者范围内不存在素数 if (start end || end 2) { return new int[0]; } start Math.max(start, 2); // 扫描区间内偶数单独处理配合 isPrime 的步进优化 ListInteger list new ArrayList(); for (int n start; n end; n) { if (isPrime(n)) { list.add(n); } } int[] result new int[list.size()]; for (int i 0; i list.size(); i) { result[i] list.get(i); } return result; } public static boolean isPrime(int n) { if (n 2) { return false; } if (n 2) { return true; } if (n % 2 0) { return false; } // 从3开始步进为2只检查奇数因子 for (int i 3; i n / i; i 2) { if (n % i 0) { return false; } } return true; } public static void main(String[] args) { System.out.println(Arrays.toString(findPrimes(1, 100))); System.out.println(Arrays.toString(findPrimes(100, 200))); System.out.println(Arrays.toString(findPrimes(200, 2))); System.out.println(Arrays.toString(findPrimes(-10, 1))); } }运行main方法输出如下[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] [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199] [] []注意这里有三处细节优化第一isPrime里把2单独返回true然后所有偶数直接返回false第二循环中把步长设为2从3开始只检查奇数因子计算量直接减半第三判断条件用了i n / i而不是i * i n彻底规避溢出风险。你会发现这个方法在判断单个素数时效率已经非常不错。如果你需要频繁地查询多个范围内的素数就把findPrimes里的逻辑替换成第4节的筛法实现方法的签名保持不变调用方完全无感。这就是把底层算法替换掉、上层接口保持不变的好处工程上叫作面向接口编程。虽然是练习题但你从一开始就养成这种习惯后面做真实项目会顺利很多。7. 实际编码中的避坑指南与性能实测数据7.1 关于ArrayList的自动装箱数据量一大性能差距就出来了很多人在收集素数时会直接写ListInteger list new ArrayList(); list.add(n);。这在小数据量时用着挺顺手但数据量一大就会暴露出两个问题。一是自动装箱。int是基本类型Integer是包装类型将int存入ArrayList时会自动装箱成一个新Integer对象。找出100万以内的素数总共要创建7万多个Integer对象虽然现代JVM做这类小对象分配很快但毕竟有额外开销。二是ArrayList的扩容机制。当内部数组容量不够时会创建一个更大的新数组通常是原来的1.5倍然后把旧数组中的元素拷贝过去。反复扩容的过程中数组拷贝的总成本也不可忽视。如果你用的JDK版本比较新而且确实要用泛型集合收集基本类型数据可以考虑用Eclipse Collections或FastUtil这类第三方库它们提供了专门针对int基本类型的集合类避免了装箱开销。不过大多数场景下ArrayList就够用了知道有这个坑即可不用过度设计。7.2 朴素法与筛法的真实性能对比口说无凭给一组我本地实测的数据JDK 17默认参数统计[2, 1000万]区间内的素数方案耗时说明双循环朴素法不加平方根优化约30秒以上每判断一个数都要除到n-1试除法加上平方根优化和偶数跳过约1.2秒秒杀前一个版本埃拉托斯特尼筛法约38毫秒性能提升非常明显分段筛法分段处理大数据范围约25毫秒优化内存局部性后略有提升是不是很惊人同样是找1000万以内的素数朴素法要半分钟而筛法只需要几十毫秒。这就是为什么我一直强调如果你在做批量查询一定要把筛法学到手如果你只是单次判断某个数是不是素数那只用试除法就行用筛法反而是浪费。还有人可能会问那Java 8的并行流能不能再压榨性能可以但要注意筛法本质上是递推标记每个合数是否被标记取决于它的质因子是否已经被处理并行化要做更多的任务拆分和合并工作。我建议普通场景先不要上并行等你真的能通过性能分析证明瓶颈在素数生成这一块再来考虑。7.3 数组工具的合理使用Arrays、System.arraycopy 与手动循环的选择返回数组之前排序、拷贝、转字符串经常会用到java.util.Arrays里提供的方法。我列一下在实际代码里最常用的几个以及它们应该用在什么场景方法功能推荐使用场景Arrays.toString(int[])将数组转成可读字符串调试时快速查看结果Arrays.copyOfRange(int[], from, to)截取数组片段范围筛选后的结果提取Arrays.fill(boolean[], val)批量填充数组筛法初始化标记数组System.arraycopy(...)高效数组复制手动扩容时替代for循环特别说一下System.arraycopy它是native方法底层由JVM直接优化性能比手动for循环好很多。如果你将来自己实现了某个动态数组结构需要考虑扩容逻辑时记得使用它而不是自己写循环逐个拷贝。这一点在面试“自己实现ArrayList”这类问题时也是加分项。8. 从这道题延伸出去的实用扩展8.1 如果面试官让你求第N个素数求指定范围内的素数和求第N个素数这两道题经常被连着问。求第N个素数有个比较聪明的方案先用素数定理估算出第N个素数大概有多大然后以这个值为上限执行一次筛法。素数定理给出的估算公式是第n个素数约等于n×ln(n)。我在工程里曾经用这个思路写过一个工具方法传入一个整数n返回第n个素数效果还不错。8.2 判断超大数素数引入米勒-拉宾概率测试如果题目变成“判断一个超过int范围的数是否为素数”那试除法和数组筛法都失效了——你不可能创建一个长度超过21亿的boolean数组。这时候业界常用的方案是Miller-Rabin素性测试它是一种概率检测算法通过对随机基底的模幂运算来判断素数速度极快出错概率可以通过增加测试轮次降到极低。Java标准库BigInteger.isProbablePrime(int certainty)底层就实现了这个算法在实际场景里可以直接用它比如RSA密钥生成时就需要快速判断随机大数是否为素数。这类扩展知识不一定每次面试都考到但如果你主攻Java后端岗位具备“知道问题边界在哪里、什么时候该换算法”的意识会给面试官留下完全不一样的印象。8.3 和字符计数、网关鉴权里那些“查重”问题的共通点如果你认真做过一些真实项目会发现素数筛选的思路其实可以迁移到很多场景里。比如Redis集群中判断一个key应该hash到哪个槽位你需要通过某种映射来分散数据再比如网关做限流时如何快速判断某个用户是否在允许列表内。这些问题的共同点在于都需要一个足够快速的查找结构来减少不必要的重复计算。判断是否是素数本质上也是一种“查重”——判断这个数是否被小于它的那个因子集合“命中”过。理解了这一点你在学布隆过滤器、位图bitmap这些数据结构的时候会轻松很多因为它们从根本上解决的是同一类问题。9. 面试中的表达要点和相关高频考点归类如果你是在准备面试过程中看到这篇博客请务必记下以下几个表达时的要点。代码写得对只是第一步能把思路讲清楚才是拿高分的关键。第一先讲边界条件。别一上来就写循环先说“我会先判断n小于2的情况直接返回false因为1和负数都不是素数”。面试官听到你第一时间考虑边界条件基本就能确定你不是新手。第二主动解释平方根优化。写完最简单的版本后主动补一句“其实这里可以优化到根号n因为如果一个合数存在因子那必然有一个不超过根号n的因子”。这个数学结论看似简单但能主动讲出来的人并不多。第三根据数据规模选择方案。如果在面试中聊到筛选指定范围内所有素数你可以说“如果范围较小我就用逐个判断如果范围较大我就会用埃拉托斯特尼筛法预处理”。这种“根据不同场景选择不同方案”的表述会让你从其他候选人中脱颖而出。这道题所在的考点大背景也很重要。面试官问Java中如何操作数组多半会连着问数组和集合的区别、Arrays工具类、ArrayList的扩容机制问素数相关算法时也可能跳到复杂度分析、二分查找这些话题。你在准备时可以把这些点串成一个知识链路来复习。10. 最后分享几个我自己实际操作中的心得这道题我写过不下十遍每次帮别人review代码时都能发现新的细节问题。想再单独叮嘱你几句都是我在真实操作里碰到的教训。一个很典型的坑是修改了判断素数的逻辑结果导致2被排除在结果之外。比如有些人为了跳过偶数遍历直接从3开始遍历并且步长设为2但忘了把2单独加进去。看起来很难发现因为大部分测试用例里少了2并不会让结果明显错误只是输出里少了第一个素数。如果你发现自己怎么调都少一个数优先看一下起点和2的处理逻辑。另一个我想强调的性能细节是在for循环里调用Math.sqrt(n)会让性能严重下降。如果写成for (int i 2; i Math.sqrt(n); i)Math.sqrt可不会自动优化成一次计算它在每次循环判断都会被重新执行。加上浮点运算的开销整个循环的性能损耗会非常明显。正确做法是用i * i n或者把Math.sqrt(n)提到循环外面用变量存起来。还有一点是关于代码可读性的。工具方法尽量做成static并且不依赖外部状态。如果你写的是某个类内部的方法尽量设计成静态工具这样在lambda表达式、Stream管道里可以直接用PrimeFinder::isPrime这种引用方式。最后想说绝大多数编程初学者都会经历一个阶段觉得这类算法题“没有实际意义”。但等你真正做项目遇到要从大量数据中快速筛选符合条件的记录、要设计一个缓存淘汰策略、要判断某个key是否在某个超大集合中时你会感谢当年认真研究过这些基础题的自己。我用了十几年Java写过的业务代码不计其数但真正让我在系统性能调优时游刃有余的恰恰是这些朴素算法里反复磨炼出来的思维功底。