素因数分解
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);
'''