素因数分解とは、数値を構成する素数を求める（素数の累乗の和で表す）ことです。例えば、９８なら2×72 と表されます。中学校や高校の数学の基本事項の一つですね。 素因数分解のアルゴリズム この素因数分解のアルゴリズムとして最も簡単なのは、その数を２からその数値の平方根までの整数で順次割って行く、という計算法でしょう。なぜ、平方根までかというと、ある整数を整数の積の形で表す時に平方根が含まれていれば、残りの数は必ず平方根以下になるからです。 まず、素因数に分解する正の整数a を２で割ってみます。２で割り切れれば、その数は２を因数に持つわけですから因数のリストに２を加えます。そして、aを２で割った数値をaに代入してさらに２で割ってみます。これで割り切れれば、因数のリストにまた２を加えます。 こうして、２で割り切れなくなるまで同じ処理を繰り返せば、その数に素因数として「2」がいくつ含まれるかわかる
