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

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

2|  90
3|  45
3|  15
     5

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

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

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

// the number of primes which is less than 1000
const int PRIME_NUM = 168;

//primes less than 1000
const int PRIME[PRIME_NUM] = {
    2, 3, 5, 7, 11,
    13, 17, 19, 23, 29,
    31, 37, 41, 43, 47,
    53, 59, 61, 67, 71,
    73, 79, 83, 89, 97,
    101, 103, 107, 109, 113,
    127, 131, 137, 139, 149,
    151, 157, 163, 167, 173,
    179, 181, 191, 193, 197,
    199, 211, 223, 227, 229,
    233, 239, 241, 251, 257,
    263, 269, 271, 277, 281,
    283, 293, 307, 311, 313,
    317, 331, 337, 347, 349,
    353, 359, 367, 373, 379,
    383, 389, 397, 401, 409,
    419, 421, 431, 433, 439,
    443, 449, 457, 461, 463,
    467, 479, 487, 491, 499,
    503, 509, 521, 523, 541,
    547, 557, 563, 569, 571,
    577, 587, 593, 599, 601,
    607, 613, 617, 619, 631,
    641, 643, 647, 653, 659,
    661, 673, 677, 683, 691,
    701, 709, 719, 727, 733,
    739, 743, 751, 757, 761,
    769, 773, 787, 797, 809,
    811, 821, 823, 827, 829,
    839, 853, 857, 859, 863,
    877, 881, 883, 887, 907,
    911, 919, 929, 937, 941,
    947, 953, 967, 971, 977,
    983, 991, 997};

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

int firstFact(int num){
    /*
        the least prime which is a factor of number
     */

    for (int i=0; i<PRIME_NUM ; i++) {
        if (num > PRIME[i] ) {
            if (num%PRIME[i] == 0) {
                return PRIME[i];
            }
        }else{
            return 0;
        }
    }
}

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

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

void factoring(int num, vector<int> * rslt){
    /*
        factoring num and the factors into rslt
     */
    int fact = firstFact(num);

    if (fact>0) {
        (*rslt).push_back(fact);
    }else{
        return;
    }

    factoring(num/fact, rslt);
    return;
}

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

90=2*3*3*5
end

と表示されます。

void printFactors(vector<int> rslt){
    /*
        print result of factoring num
     */

    int num = 1;
    for (vector<int>::iterator it=rslt.begin(); it!=rslt.end();it++){
        num *= (*it);
    }

    cout << num << " = ";

    for (vector<int>;::iterator it = rslt.begin(); it != rslt.end(); it++) {
        cout << (*it);
        if(it+1 != rslt.end()){
            cout << "*";
        }else {
            cout << endl;
        }
    }

    printf("endn");
}

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

void main(){
    int number;
    vector rslt;

    cout << "1000以下の自然数を入力してください。" << endl;
    cin << number;

    factoring(number,&rslt);

    printFactors(rslt);
}

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

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