「数論入門I 」より引用します。

n番目の素数 Pn の単純な一般式はあるか？ (すなわち、与えられた
nに対してエラトステネスのふるいよりも楽に Pn の値を計算できる公式が
あるか？)
そのような公式は知られていないし、そのような公式はありそうもない。
一方、様々な Pn の「公式」を考案することはできる。これらのうち、あ
るものは Pn をそれ自身を用いて定義しており、従来知られていない Pn の
値を計算することができないので、ほんの興味をそそるものにすぎない。定
理 419 において例を与える。他のものは理論的には Pn を計算することがで
きるが、エラトステネスのふるいよりも実質的に多くの労力を払うことによっ
てのみ可能である。 その他のものはエラトステネスのふるいとなお本質的に
同等である。

要はエラトステネスが最良のアルゴリズムであるということが証明されてるみたいです。