少し補足しておく。

正の実数xに対して、x以下の素数の個数をπ(x)と表す。
0＜r＜1なる適当なrに対して、π(x)の計算量がO(x^r)で済むと仮定する。
このとき、n番目の素数を求める計算量はO(x)より小さなオーダーで済む。
これは次の理由による。


π(x−1)＜π(x)＝n　…(*)　を満たす自然数xに対して、
xは「n番目の素数」であることが分かるから、(*)を満たす
自然数xを求めればよい。
記述量の省略のため、以下ではm＝nlog(n)＋nloglog(n)と置いておく。

まず、>129のピエール・デザルトの欄により、n≧6のときp(n)＜m
が成り立つから、(*)を満たすxは区間[1, m] の中に存在する。
そこで、まずはπ(y)＝nを満たす自然数yを[1, m]の中から探す。
関数πは広義単調増加だから、区間[1, m]について二分探索を使えば、
πの計算を高々log[2](m) 回行えば、π(y)＝nを満たす自然数yが取れる。

二分探索
ttp://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2