今日は素因数分解のプログラムを紹介します。言語はC++です。素因数分解を行っていて、再帰プログラムでかけるのではないかと考えて、苦手だった再帰プログラムの練習として作ってみました。

通常、人間が手で素因数分解をやるようなアルゴリズムでコンピュータに素因数分解を行って行きます。例えば、90という数字を素因数分解をするとき、

となり、90=233*5と計算できます。つまり、ある数の最小の素因数を見つけ、それを見つけたら、その数をその素因数で割り、その割った値に対して同様な作業を繰り返しています。

それをプログラムにしていきましょう。
<キーワード> 素因数分解, C++, アルゴリズム, 再帰処理, プログラム

まず、素数のリストを作ります。素数のリストは適当に作ります。最悪、手打ちでもいいでしょうw

それでは、最初の素因数を手に入れる函数を作りましょう。
素因数は素因数分解される数より大きくなることはないので、num<PRIME[i]になったとき、0を返します。
もし、num>PRIME[i]のとき、numが割り切れるかどうかを確認し、割り切れれば、その値を返し、そうでなければ、次の素数に対して同様の操作を繰り返します。

実際に素因数分解する処理です。
factという変数に素因数分解される数の最小の素因数を入れます。
ここで、素因数分解できなかったときは0が返ってくるので、fact=0のとき、このプログラムは終了します。
fact>0のときはrsltという素因数を保存しておく配列に入れます。

その後、num/factに対して再帰的に素因数分解を行います。

これは表示させる函数です。
rsltをもらって、例えば、その配列が{2,3,3,5}であれば、

と表示されます。

実際に動かすmain函数は適当にこんなふうに作ればテストできます。

今回はそのまま単純にプログラムを作ってみました。
しかし、数nの素因数をpとすると、必ず、p^2<=nが成り立つことを利用して、冗長さを減らし、もう少し計算量を少なくすることができます。

もっと早い、あるいはわかりやすいアルゴリズムがあれば、是非教えて下さい。