Posted at

エラトステネスの篩

素数を求めるアルゴリズム「エラトステネスの篩」をJavaScriptで書いてみたので投稿してみる。

function GetPrimeNumbers (m) {

//配列をつくって 0 と 1 にはあらかじめ null としておく。
var t = (new Array(m)).fill(0).map((v, i) => i);
t[0] = null;
t[1] = null;

//エラトステネスの篩 で素数の添字に null セット
for (var i = 2; (i * i) < m; i++) {
var p = i << 1;
while (p < m) {
t[p] = null;
p += i;
}
}

//nullを配列から除去して返す
return t.filter(v => v);
}

//100までの素数を出力
console.log( GetPrimeNumbers (100) );
// [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]

以上!