为何while(k*k <= n)比while(k <= Math.sqrt(n))更优？

这个问题在素数判断的代码里太常见了，我来拆解一下背后的原因，再聊聊提前缓存Math.sqrt(n)的情况：

一、原始写法的差异：函数调用与运算开销 #

首先，你猜的没错——重复调用Math.sqrt(n)确实会带来额外开销。Math.sqrt()是标准库函数，每次调用都要经历函数调用的常规流程：栈帧创建、参数传递、执行浮点数平方根运算、返回结果。而k*k只是一次整数乘法运算，CPU执行这类算术操作的速度远快于“函数调用+浮点数运算”的组合。

如果是在循环里每次都调用Math.sqrt(n)（没提前缓存结果），这个开销会被循环次数放大，差距会更明显。

二、提前缓存Math.sqrt(n)的情况：效率与正确性的权衡 #

你提到的提前计算sqrt_n = Math.sqrt(n)再复用的写法，确实能解决重复函数调用的问题，但和k*k <=n对比，得从两个维度看：

1. 效率对比 #

如果n的范围在浮点数能精确表示的范围内（比如int或long类型的n，且n ≤ 2^{53——因为double类型的精确整数范围上限是2}53），提前缓存sqrt_n后，循环里的k <= sqrt_n和k*k <=n效率差距其实不大。不过k*k是纯整数运算，不需要把整数k转成浮点数再比较，所以理论上会略快一点，但实际大多数场景下，这点差距可以忽略不计。

2. 正确性风险 #

这里有两个关键问题：

• 浮点数精度问题：当n非常大（超过2^53），Math.sqrt(n)的结果会因为浮点数精度限制无法精确表示真实平方根。比如n是一个超大完全平方数，但Math.sqrt(n)可能被近似成比真实值小一点的数，导致循环提前结束，漏判情况。而k*k <=n是纯整数运算，只要k和n的类型能容纳运算结果（比如用long而非int），就不会有精度问题。
• 整数溢出问题：如果k是int类型，当k足够大时，k*k会超出int的最大值，变成负数，这时候k*k <=n的判断会出错（负数肯定小于正数n），导致循环异常。而提前缓存sqrt_n的写法就不会有这个问题，因为k是和浮点数比较，不会触发整数溢出。

三、总结怎么选？ #

• 如果n的范围不大（比如日常算法题里的素数判断，n在int或long的安全范围内），提前缓存sqrt_n是不错的选择，兼顾效率和安全性。
• 如果n是超大整数，或者你想完全规避浮点数相关风险，k*k <=n更可靠（但要注意用足够大的整数类型，比如long存储k*k的结果，避免溢出）。
• 绝对不要在循环里每次都调用Math.sqrt(n)，这是完全没必要的性能浪费。

内容的提问来源于stack exchange，提问作者Hatik