素数判定速度

Haskellによる素数無限リスト実装で、nが素数かどうかの判定にx * x <= nという式を用いたことで高速化されたと書いた。だけれども、それってどこまで高速化に貢献してるのかなあと思ったので、考えてみた。
例えば、10000前後の素数があったときに、どれだけのコストが無駄になるのだろうか。10000までの素数の個数は1229であり、100までの素数の個数は25だから、大体50倍くらいになる。で、xまでの素数の個数というのは素数定理によればx / log(x)で表現されるらしいので、xまでの素数とsqrt(x)までの素数の個数の関係は、sqrt(x) / 2倍となる(計算は省略)。つまり、後半になればなるほど素数だったときのコストはかかるのだ。
問題は、素数ではない場合だ。この場合に、どの程度の比較の回数がかかっているかによって、平均的な比較回数の見積もりができる。だけれども、それは非常に面倒で仕方がない上に、それを示すだけの数学的な能力がない。
うーん、もうちょっと考えてみよう。