【アルゴリズム】素数判定をjavascriptで実装する
素数ってなに?
1と自分以外でしか割り切れない数です。自分自身以外に、正の約数を持たないとも言います。
1,2,3,5,7,11
みたいな。
4,6,10 はダメです。例えば「4」は「1より大きい整数」ですが「1と4以外にも2で割り切れる」ので、素数ではありません。
シンプルに真偽判定するプログラムを書いてみました。
ポイントは、自分自身以外で割り切れる数を見つけられるかどうかです。
逆に言うと倍数を見つければいいわけですね。
function primeNumber(n) {
if (n === 2) return true;
for (let i = 2; i < n; i++) {
if (n % i === 0) return false;
}
return true;
}
エラトステネスのふるい
function sieveOfEratosthenes(n) {
var primes = [];
for (let i = 0; i <= n; i++) {
primes[i] = true;
}
primes[0] = false;
primes[1] = false;
for (let i = 2; i <= Math.sqrt(n); i++) {
for (let j = 2; j * i <= n; j++) {
primes[i * j] = false;
}
}
var result = [];
for (let i = 0; i < primes.length; i++) {
if (primes[i]) result.push(i);
}
return result;
}
エラトステネスのふるいと言う、有名な素数を見つけ出すアルゴリズムがあります。これも考えた方は一緒です。以下の処理で、倍数を作り出して、該当する値をfalseにしてます。
for (let i = 2; i <= Math.sqrt(n); i++) {
for (let j = 2; j * i <= n; j++) {
primes[i * j] = false;
}
}
エラトステネスのふるいは、この本でも登場します。気になる人は読んでみよう。
この記事が気に入ったらサポートをしてみませんか?