JavaScriptで素数を列挙する

ある問題を解くために素数が必要になったので、JavaScriptで素数を列挙する方法を考えてみました。
最も小さい素数は2で、次は3です。配列にセットします。
そして5,7,9,11と奇数について順に素数であるか確認していきます。
5が「5未満の素数」で割り切れるか確認します。実際は5の2乗根以下の素数について確認すれば十分です。これを超える素数では5を割り切れないからです。したがって「2乗して5以下の素数」で割り切れるか確認します。「2乗して5以下の素数」である2で割り切れないので5は素数です。配列にセットします。
7が「2乗して7以下の素数」で割り切れるか確認します。2で割り切れないので7は素数です。配列にセットします。
9が「2乗して9以下の素数」で割り切れるか確認します。2で割り切れないですが、3で割り切れるので9は素数ではありません。
11が「2乗して11以下の素数」で割り切れるか確認します。2,3で割り切れないので11は素数です。配列にセットします。
これを繰り返します。

function prime(n) {
  //n未満の素数を配列で返す。
  var ps, x, flg, j;
  ps = [2, 3];
  for(x = 5; x < n; x += 2) {
    flg = 0;
    for(j = 0; ps[j] * ps[j] <= x; j++) {
      if(x % ps[j] == 0) {
        flg = 1;
        break;
      }
    }
    if(flg == 0) {
      ps.push(x);
    }
  }
  return ps;
}

コメント

タイトルとURLをコピーしました