素数を求める

素数のテーブルを作る

javascript で素数を求めるプログラムを書いてみました。特にテクニカルなことはやっていません。小さい数からその倍数を消していくという総当り方式です。

getsosu.js

// mSosuは得られた素数のテーブルのポインターです。
    var mSosu=null;
// nn より小さい数で素数となるものを探します。
    function fSosu(nn){
        var i,j,k,m;
        var cnt=0;
        var temp =Array(nn);
        for(i=0; i<nn; i++) temp[i]=0;
        m = Math.floor(Math.sqrt(nn)); // ルートnnまでチェックします。

        for(i=2; i<=m; i++){
            if(temp[i]==1) continue;
            k=Math.floor(nn/i);　// i*k までチェックします。
            for(j=2; j<=k; j++){
                temp[i*j]=1; // i*j は素数ではありません。
            }
        }

        for(i=2; i<nn; i++) if(temp[i]==0) cnt++; //素数の数
        mSosu = new Int32Array(cnt); //テーブルのメモリー確保

        for(i=2,j=0; i<nn; i++){
            if(temp[i]==0){ //テーブルに素数を格納
                mSosu[j]=i; j++;
            }
        }

        return cnt;
    }

どこまで大きなテーブルを作れるか？

nn にどこまで大きな数字を入れることができるか、計算時間とともにチェックしました。

check.js

    var nn=2;
    for(var i=0; i<25; i++){
        nn*=2;
        var start_ms = new Date().getTime();
        if (!fSosu(nn) ) break;
        var elapsed_ms = new Date().getTime() - start_ms;
        console.log(nn + ' : ' + mSosu.length + ' : ' + elapsed_ms);
    }

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

で計算したところ、nn = 67108864 は10秒前後で計算が終了ます。
しかし、nn=134217728はエラーでChromeが落ちます。