素数ってなに？

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;
   }
 }

エラトステネスのふるいは、この本でも登場します。気になる人は読んでみよう。