【JavaScript】エラトステネスの篩を書いてみた

定本Javaプログラマのためのアルゴリズムとデータ構造

を読んでいたところ「エラトステネスの篩」という単語が出てきたので気になって調べてみた。

エラトステネスの篩とは

エラトステネスの篩（エラトステネスのふるい）は、指定された整数以下の全ての素数を発見するための単純なアルゴリズムである。古代ギリシアの科学者、エラトステネスが考案したとされるため、この名がある。(Wikipedia)

アルゴリズム

1. 探索リストに2〜nまでの整数を昇順でいれる
2. 探索リストの先頭の数を素数リストに移動し、その倍数を探索リストからふるい落とす
3. 上記のふるい落としを探索リストの先頭値 >= nの平方根　まで続ける
4. 探索リストに残った数を素数リストに移動して処理終了(Wikipedia)

例えば、n = 10とすると、 【1】 探索リスト = {2,3 〜 10}

【2-1】(素数リストの先頭「2」の倍数をふるい落とす) 素数リスト = {2} 探索リスト = {3,5,7,9}

【2-2】(素数リストの先頭「3」の倍数をふるい落とす) 素数リスト = {2,3} 探索リスト = {5,7}

【4】(探索リストの先頭「5」がn=10の平方根より大きくなったため処理終了) 素数リスト = {2,3,5,7}

実装

var MAX = 100;
var sieve = new Array(MAX);

//全ての数に対して素数フラグを立てる
for (var i = 0; i < MAX; i++) {
    sieve[i] = true;
}
//最大値の平方根を計算
var max = Math.floor(Math.sqrt(MAX));

//0,1は素数でないので外す
sieve[0] = false;
sieve[1] = false;

//探索リストの先頭 >= MAXの平方根まで、素数リストの倍数をふるい落としていく
for(var i = 2; i <= max; i++) {
    //素数だったら
    if(sieve[i] === true) {
        //その倍数をふるい落とす
        for(var j = i * 2; j <= MAX; j += i) {
            sieve[j] = false;
        }
    }
}

//素数の出力
for(var i = 0; i < MAX; i++) {
    if(sieve[i] === true) {
        console.log(i);
    }
}

参考

エラトステネスの篩 - Wikipedia