素因数分解のやり方
ある自然数を素数の小さい数から割り続けて（割り切れない場合は次に小さい素数で割り続ける。）、
その素数の積で表現したものです。
例として自然数360を素因数分解すると2 x 2 x 2 x 3 x 3 x 5 = 23 x 32 x 5となります。
素数の計算は次の通りです。
素数の計算（エラトステネスのふるいの計算）
- 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以下の素数）回だけ上記のふるい落とす操作を行うことになります。
|