n 番目の素数と素数の個数

$n$ 番目の素数と、決めた上限までに素数がいくつあるかを求めます。エラトステネスの篩を使います。

2 から順に数を並べ、2 の倍数、3 の倍数、5 の倍数 … と消していきます。消し残ったものが素数です。1 つずつ試し割りするより、まとめて速く数えられます。

例

100 番目の素数は 541 です。1000 以下の素数は 168 個あります。10000 以下なら 1229 個、100000 以下なら 9592 個で、大きくなるほど素数はまばらになります。

素数の個数の目安

$x$ 以下の素数の個数は、おおよそ $\dfrac{x}{\ln x}$ 個になります。これを素数定理といいます。

$x = 1000$ なら $1000 \div 6.91 \approx 145$ で、実際の 168 に近い値です。$x$ が大きくなるほど、この見積りの相対的な誤差は小さくなります。

注意

篩は上限のぶんだけ場所を使うので、$n$ は 50000 まで、数える上限は 1000000 までにしてあります。

1 は素数ではありません。素数は 2 から始まります。