判断质数的Java方法：循环与模运算教程

本文深入解析了判断质数时循环上限的优化原理，指出只需遍历到√n而非n/2——因为若n有大于√n的因子，其对应的小因子必然已在此前被检测到，继续循环至n/2将导致近一倍的冗余计算，严重影响大数（如10⁶级别）性能；同时提供了两种实用实现方案：使用(int)Math.sqrt(n)确保精度，或采用i*i≤n避免浮点误差，是Java初学者提升算法效率的关键实践指南。

判断质数时为什么不能只循环到 n/2

因为质数的最小非平凡因子一定 ≤ √n。比如 100 的因子对是 (2,50)、(4,25)、(5,20)、(10,10)，一旦超过 √100=10，就只是前面的镜像。循环到 n/2 会多跑近一倍无意义的迭代，尤其对大数（如 10⁶ 级）明显拖慢。

实操建议：

• 循环上限统一用 (int) Math.sqrt(n)，注意强制转 int 避免浮点误差
• 别写 i * i —— 虽然数学等价，但对超大 n（接近 Integer.MAX_VALUE）可能溢出，i 更安全
• 单独处理 n == 2 和 n ：小于 2 的数（0、1、负数）都不是质数；2 是唯一偶质数

isPrime(int n) 函数里最容易错的边界情况

很多人写完逻辑，一测就翻车：输入 0、1、2、4 或负数时返回错误结果。这不是算法问题，是没厘清定义。

质数定义是「大于 1 的自然数，且只有 1 和它本身两个正因数」——所以：

• n 直接返回 false（包括 0、1、负数）
• n == 2 返回 true（唯一要特判的偶数）
• n % 2 == 0 && n != 2 直接返回 false（排除其余所有偶数）
• 后续循环只需检查奇数因子：for (int i = 3; i

用 long 型判断大数时的陷阱

如果把函数改成 isPrime(long n)，表面看更通用，但实际埋了两个坑：

• Math.sqrt(long) 返回 double，而 double 对超过 2⁵³ 的整数无法精确表示，会导致开方后向下取整出错（比如 Math.sqrt(9007199254740993L) 就不准）
• 循环变量仍用 int i 会溢出——当 n 接近 Long.MAX_VALUE 时，sqrt(n) ≈ 3×10⁹，超出 int 范围（2³¹−1 ≈ 2.1×10⁹）
• 正确做法：用 long i 做循环变量，并改用 i * i 判断（虽有乘法开销，但避免了浮点不精确）

性能敏感场景下要不要预筛小质数

如果批量判断多个数（比如 10⁵ 个 ≤ 10⁶ 的数），每次都从头循环开方，不如提前用埃氏筛生成 boolean[] isPrime 查表。但单次判断或数很少时，预筛反而浪费内存和初始化时间。

简单取舍建议：

• 单个数、n ：直接试除，代码短、无依赖、易维护
• 批量判断、n 集中在某区间（如 [1, 10⁶)）：用埃氏筛预处理，查表 O(1)
• 数很大（> 10⁹）且量少：考虑 Miller-Rabin 概率算法，但 Java 标准库没内置，需引入第三方或手写，误判率可控但非绝对准确

真正难的不是写对一个 isPrime，而是想清楚你面对的是单次校验、批量预处理，还是高并发低延迟服务里的热路径——选错策略，优化就跑偏了。

以上就是本文的全部内容了，是否有顺利帮助你解决问题？若是能给你带来学习上的帮助，请大家多多支持golang学习网！更多关于文章的相关知识，也可关注golang学习网公众号。