c++ - 平方根を 1 回実行するのは、2 乗を n 回実行するよりも遅いですか?

Question

私は素数のいくつかのアルゴリズムを見ていましたが、これに出くわしました:

for(int i=2;i*i <= n;i++)
{/*assume no operations here*/} 

上記のループが次のループよりも高速になるかどうか疑問に思っていましたか?

int x=sqrt(n);
for(int i=2;i<=x;i++)
{/*nop*/}

Answer 1

nもちろん、の値にもよります。とにかく、sqrt()正しい結果が得られるとは限りません。丸めの理由により、値がx予想より1つ小さくなり、アルゴリズムが台無しになる可能性があります。微妙な最適化を行うのではなく、ここでは正確さに固執し、正しい結果が得られることが保証されている元のバージョンを使用します。