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;
}
//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;
}
[ 2017年1月8日 | カテゴリー: JavaScript | タグ: アルゴリズム , 素数 ]
« 丸源ラーメン 八王子南大沢店 | 2018年は2つの素数の2乗の和、70年間で今年だけ！ »
コメントを残す