ある整数の素因数分解を考える時、すぐ思いつくのはその整数以下の素数で次々割っていくという方法です。 が、これだとまず素数を求める必要があり、これが厄介です。
そこで次に以下の様に、素因数分解したい数を2から整数の平方根までの数で次々割っていくという方法が考えられます。
(素朴試し割り法)
なおここで紹介している方法は、最も単純な方法で素因数分解の方法としてはもっと洗練されたものがたくさんあります。
素因数分解したい数 N を、まず一番小さな素数である2で割ります。
割り切れたら商( N/2 )をまた2で割ります。これを2で割り切れなくなるまで繰り返します。
この操作の結果残った数 R には素数2と2から作られる合成数(素数の積で表される数)は含まれなくなります。
素数2で割る操作の結果残った数を次に小さい素数3で割ります。これを3で割り切れなくなるまで繰り返します。
この時点で、残った数には素数3とその合成数も含まれなくなります。
これを4以降、素因数分解したい数 N の平方根まで繰り返します。途中で割られる数 R が1になった場合はそこで終了します。
このとき割る数が素数かどうか確認する必要はありません。
何故なら割る数 j が素数でない場合、j は j より小さい素数の合成数になっているので (例えばjが4なら、4は素数2で2*2と表される) 、
割られる数 R は j を構成する素数で割り切った残りだから割る事が出来ないので割る数 j に素数でない数が
入っていてもいなくても同じになります。
N の平方根まで割る操作を繰り返したあとでも(1以外の)数字が残った場合、それは素数になります。
理由は下の(ii)で説明してあります。
割る数が、素因数分解したい数の平方根まででいいのは以下の理由によります。
素因数分解したい数Nの平方根をrnとしNを2からrnまでの数で割り切れなくなるまで残ったのこりを
Rとします。
このとき残った数Rは、素数になっています。
何故ならRが素数でない場合はRは素数 p とある整数 i の積 R = i*p で表される事になりますが、
このときp , i ともに rn より大きい数になります。
またRはNの因数なので当然Nより小さい数です。従って
次の式が成り立ちます。
N > R = i*p > rn*rn = N
これは矛盾です。従ってRは素数となり素朴試し割り法では素因数分解したい数の平方根までの 数でわればいい事になります。
以上の方法を使って作ったプログラムを下に載せておきます。(C++ で書いてあります)
素因数分解をおこなっているのは関数 Factorize_To_PrimeFactor の部分でこの関数の引数に
素因数分解したい整数(unsigned long型)を与えます。
Factorize_To_PrimeFactor の中で整数の割り算を繰り返す部分が関数 Devide_PrimeFactor で、
第一引数にあたえた整数が、第二引数であたえた整数で割り切れなくなるまで割り算を繰り返します。
割り切れなくなったら、割った残りの部分が第一引数で呼び出し側( Factorize_To_PrimeFactor )にかえります。
整数の割り算を繰り返すところ( Factorize_To_PrimeFactor の中 )で2の部分だけ分けてありますが、これは2で割り切った後のこりは
偶数でわる必要がないので2でまず割り切って残りは奇数だけで割るようにしたためです。
/*
整数の素因数分解プログラム 単純に小さい方から素数で割っていく */
using namespace std; //introduces namespace std /*
/*
/*
//前処理(0と1をのける)
unsigned long max_limit = sqrt( the_target
) ; //上限値の計算
//2で割る
return 1; } /*
*/
if( (*the_target) %
divide_index == 0 ){//割り切れる
if(the_power !=0 ){//割れた場合、数^冪
を文字列へ出力
return 0 ;//divide_index では割れなかった
|