质数筛选核心优化包括：只试除到√n、跳过偶数（2单独处理）、用已知质数表试除，大范围推荐埃氏筛法，时间复杂度O(n log log n)。
输出指定范围内的所有质数，关键在减少不必要的判断次数。核心优化思路是：跳过明显非质数、限制试除上限、利用已知质数加速验证。
只检查到平方根
判断一个数 n 是否为质数时，无需从 2 试除到 n−1，只需检查到 √n 即可。因为若 n 有大于 √n 的因子，必然对应一个小于 √n 的配对因子。
例如：判断 49，只需试除 2 到 7（√49 = 7），发现 7×7=49，即可判定非质数；不需要再试 8~48。
跳过偶数和 2 单独处理
除了 2，所有偶数都不是质数。因此可以：
立即学习“Java免费学习笔记（深入）”；
deep-java-review
下载
Java项目代码review工具。分析Git变更+完整调用链路上下文，推断业务需求，进行多维度评分和分类汇总，生成完整PRD文档。包含细粒度Java代码审查清单（Null安全、异常处理、Streams、并发、equals/hashCode、资源管理、API设计、性能、MyBatis/ORM、事务边界、SQL/DD...
- 先单独输出 2
- 后续只遍历奇数（如 3, 5, 7, …）
- 试除时也只用奇数（跳过所有偶数除数）
用已知质数表试除（进阶）
在范围内逐个判断时，不必每次都用全部整数去试除。可维护一个已找到的质数列表，后续每个新数只用这些质数去试除（且仍只需试到 √n）。
例如：已知质数有 [2,3,5,7]，判断 29 时，只用 2,3,5,7 去除（且 √29 ≈ 5.3，所以实际只用到 5），更快更精准。
埃氏筛法（适合大范围批量求质数）
如果范围较大（比如 2 到 100000），推荐直接用埃拉托斯特尼筛法（Sieve of Eratosthenes），时间复杂度 O(n log log n)，远优于逐个判断的 O(n√n)。
基本做法：
- 创建布尔数组 isPrime[0..n]，初始全为 true
- isPrime[0] = isPrime[1] = false
- 从 2 开始，若 isPrime[i] 为 true，则将 i², i²+i, i²+2i… 标为 false
- 最后所有 isPrime[i] == true 的 i 就是质数
注意：i 从 2 遍历到 √n 即可，i² 超出范围时停止标记。
