素因数分解の方法

　ある整数の素因数分解を考える時、すぐ思いつくのはその整数以下の素数で次々割っていくという方法です。が、これだとまず素数を求める必要があり、これが厄介です。

　そこで次に以下の様に、素因数分解したい数を2から整数の平方根までの数で次々割っていくという方法が考えられます。 (素朴試し割り法)

　なおここで紹介している方法は、最も単純な方法で素因数分解の方法としてはもっと洗練されたものがたくさんあります。

(i)素朴試し割り法の手順

　素因数分解したい数 N を、まず一番小さな素数である２で割ります。

　割り切れたら商( N/2 )をまた2で割ります。これを２で割り切れなくなるまで繰り返します。
　この操作の結果残った数 R には素数2と2から作られる合成数(素数の積で表される数)は含まれなくなります。

　素数2で割る操作の結果残った数を次に小さい素数3で割ります。これを3で割り切れなくなるまで繰り返します。
　この時点で、残った数には素数3とその合成数も含まれなくなります。

　これを4以降、素因数分解したい数 N の平方根まで繰り返します。途中で割られる数 R が１になった場合はそこで終了します。
このとき割る数が素数かどうか確認する必要はありません。

　何故なら割る数 j が素数でない場合、j は j より小さい素数の合成数になっているので (例えばｊが4なら、4は素数2で2*2と表される) 、割られる数 R は j を構成する素数で割り切った残りだから割る事が出来ないので割る数 j に素数でない数が入っていてもいなくても同じになります。

　N の平方根まで割る操作を繰り返したあとでも(1以外の)数字が残った場合、それは素数になります。
　理由は下の(ii)で説明してあります。

(ii)割る数の最大値について

　割る数が、素因数分解したい数の平方根まででいいのは以下の理由によります。

　素因数分解したい数Nの平方根をrnとしNを2からrnまでの数で割り切れなくなるまで残ったのこりを Rとします。
　このとき残った数Rは、素数になっています。
　何故ならRが素数でない場合はRは素数 p とある整数 i の積 R = i*p で表される事になりますが、このときp , i ともに rn より大きい数になります。
　またRはNの因数なので当然Nより小さい数です。従って次の式が成り立ちます。

　これは矛盾です。従ってRは素数となり素朴試し割り法では素因数分解したい数の平方根までの数でわればいい事になります。

(iii)プログラムの例

　以上の方法を使って作ったプログラムを下に載せておきます。(C++ で書いてあります)

　素因数分解をおこなっているのは関数 Factorize_To_PrimeFactor の部分でこの関数の引数に素因数分解したい整数(unsigned long型)を与えます。

　Factorize_To_PrimeFactor の中で整数の割り算を繰り返す部分が関数 Devide_PrimeFactor で、第一引数にあたえた整数が、第二引数であたえた整数で割り切れなくなるまで割り算を繰り返します。
割り切れなくなったら、割った残りの部分が第一引数で呼び出し側( Factorize_To_PrimeFactor )にかえります。

　整数の割り算を繰り返すところ( Factorize_To_PrimeFactor の中 )で2の部分だけ分けてありますが、これは2で割り切った後のこりは偶数でわる必要がないので２でまず割り切って残りは奇数だけで割るようにしたためです。

/*
     整数の素因数分解プログラム

     単純に小さい方から素数で割っていく

*/
#include <iostream>
#include <string> //stringクラス使用のため
#include <sstream> //ostringstream 使用のため

using namespace std; //introduces namespace std

/*
Function prototype declaration
*/
int Factorize_To_PrimeFactor(unsigned long ) ;
int Devide_PrimeFactor(unsigned long* ,long ,string& ) ;

/*
   main function
*/
int main( void )
{
    unsigned long the_original ;
    int the_judge = 1 ;

       while( the_judge ){
      cout << "素因数分解したい数(整数)を入れてください\n" ;
      cin>> the_original;

      if( !Factorize_To_PrimeFactor(the_original ) )
        cout<<the_original<<"は、素因数を持ちません\n" ;

      cout<<"計算を続けますか? yes --> 1 / No -->0\n" ;
      cin>> the_judge ;
      cout<<" **************************\n";
    }

return 0;
}

/*
     整数の因数分解をおこなう
*/
int    Factorize_To_PrimeFactor(unsigned long the_original )//分解対象整数
{
    unsigned long the_power =0 ;
    string   prime_factor ;
    unsigned long the_target = the_original ;

//前処理(0と1をのける)
if( the_target ==1 || the_target == 0) return 0 ;//素数ではない

    unsigned long max_limit = sqrt( the_target ) ; //上限値の計算

       //max_limit は整数なので二乗しても元の数より小さい場合がある
       if( the_target > max_limit*max_limit )
         max_limit++ ;

    //2で割る
       Devide_PrimeFactor( &the_target , 2, prime_factor ) ;

     //残りは奇数のみ(上で2とその倍数は除去される)
    int roop_index ;
       for( roop_index = 3 ; roop_index <= max_limit ; roop_index +=2 )
         Devide_PrimeFactor( &the_target , roop_index , prime_factor ) ;

       if( the_target !=1){//割り切れずに残った-->これは素数になっている
         ostringstream outp_pfac ;
         outp_pfac<< the_target ;
         prime_factor += outp_pfac.str();
       }
       else{
         unsigned long the_length =prime_factor.length() ;
         prime_factor.erase( the_length-1) ;//最後の * を消す
       }

       //結果を出力
       cout<< the_original <<" = "<<prime_factor<<"\n" ;

return 1;

}

/*
対象整数を、整数で割る

*/
int    Devide_PrimeFactor(unsigned long *the_target ,   //分解対象整数
                          long          divide_index , //*the_target を割る数
                          string&       prime_factor ) //結果収容文字列
{
    unsigned short the_flag = 1 ;
    unsigned long the_power =0 ;

       while(the_flag && *the_target!=1 ){//divide_indexで割り切れるか、1にならない限り割り続ける

         if( (*the_target) % divide_index == 0 ){//割り切れる
           ( *the_target ) /= divide_index ;
           the_power++ ;
         }
         else
           the_flag = 0 ;//while ループから抜ける

       }//while 終り

       if(the_power !=0 ){//割れた場合、数^冪を文字列へ出力
         ostringstream outp_pfac ;
         outp_pfac<<divide_index ;

         if( the_power !=1 )//冪が１以外の場合(1の時は冪を表示せず)
           outp_pfac<<"^"<<the_power ;

         outp_pfac<<"*" ;

         prime_factor += outp_pfac.str();
         return 1 ;//割れた
       }

return 0 ;//divide_index では割れなかった
}

素因数分解の計算

(i)素朴試し割り法の手順

(ii)割る数の最大値について

(iii)プログラムの例