素数計算（エラトステネスのふるいの計算）
- 2からnまでの整数を並べるて素数候補の集合を作る。
- 素数候補集合の数の中で一番小さいものを新たにp とおき、
p以外のpの倍数を全て消していく。
- 上記の操作を繰り返していき、p が √nを越えたら終了。
最終的に残ったものが素数。
例としてn=30の場合では
- 素数候補の集合を A とおく。 A = { 2,3⋯ ,30 }
- p = 2 の倍数をふるい落とす。 A = { 2,3,5,7,9,11,13,15,17,19,21,23,25,27,29 }
- p = 3 の倍数をふるい落とす。 A = { 2,3,5,7,11,13,17,19,23,25,29 }
- p = 5 の倍数をふるい落とす。 A = { 2,3,5,7,11,13,17,19,23,29 }
- p = 7となるが √30 より大きいので終了。
候補の数はp として選ばれる前にふるい落とされるので、
p として選ばれるのは素数のみで、
（√n以下の素数）回だけ上記のふるい落とす操作を行うことになります。
|