素因数分解やってみた

素因数分解

Wikipediaに読んでみると、「ある正の整数を素数の積の形で表すこと」である、とのことです。先の記事で素数を求めましたので、今度は素因数分解をやってみました。

init.js

// mSosuは得られた素数のテーブルのポインターです。
    var mSosu=null;
// mSosuCntは得られた素数の数が入っています。
    var mSosuCnt=0;

方法は簡単。ひたすら割ってみて、割れたら因数とします。次の関数は、素数テーブルの小さい値から割ってみて、割れたらその数を、割れなかったら -1 を返します。

nextInsu.js

// 
    function NextInsu(nn){
        var rst=-1;
        var mm=Math.floor(nn/2);//割る数は割られる数の半分までとします。
        for(var i=0; i<mSosuCnt; i++){
            if(mSosu[i]>mm) break;
            if(!(nn%mSosu[i])){
                rst=mSosu[i];
                break;
            }
        }
        return rst;
    }

NextInsu(nn)を呼び出す側で、因数配列を作成します。

insu.js

    var mInsu=[]; //因数のバッファー
    function fInsu(nn){
        mInsu=[];
        var mm=-1;
        while(1){
            mm=NextInsu(nn);
            if(mm==-1){
                mInsu.push(nn);
                break;
            }
            mInsu.push(mm);
            nn/=mm;
        }
    }

計算時間を計ってみた

65536までの素数テーブルを作成し、2 から131072の数字の素因数分解を行い時間を測定しました。

私の環境
- Windows 7 32bit
- Intel Core i5 M450 @2.4GHz
- Chrome 67

で計算したところ 6secから7sec の時間がかかりました。

test.js

    mSosuCnt=fSosu(65536);
    var start_ms = new Date().getTime();
    for(var i=2; i<=131072; i++){
        fInsu(i);
    }
    var elapsed_ms = new Date().getTime() - start_ms;
    console.log(mInsu.length + ' : ' + elapsed_ms);
'''