LoginSignup
0

More than 5 years have passed since last update.

エラトステネスの篩

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]

以上!

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0