少数

1課自分を弱点とするすべての自然数(2,3,5,7,11...)と言います.

よくある素数判別方法

一般に、小数は以下のように判別できる.

function isPrime(x) {
  for (let i = 2; i < x; i++) {
    if (x % i === 0) return false;
    return true;
  }
}

console.log(isPrime(100));
console.log(isPrime(99));

2から、自分の1つの数字を発見すれば、少数ではありません.
しかし、この方式は2から自分の直前まで、すべての状況が順番に確認され、時間の複雑さはO(N)であり、効率的ではない.

より効果的な方法

一般的に、すべての数の約数は対称です.例えば、10は2 x 5 = 5 x 2であり、約数対称である.
ここから,数値の平方根が弱いかどうかを検証するだけで少数を判別できることが分かる.

function isPrime(x) {
  let end = Math.sqrt(x);
  for (let i = 2; i < end; i++) {
    if (x % i === 0) return false;
    return true;
  }
}

console.log(isPrime(100));
console.log(isPrime(99));

特定の数字の平方根のみをチェックしても,約数の対称性に基づいて少数の判別が可能である.

エラトステネスのふるい

一度に大量の少数を判別するには、より効果的な方法が必要です.このとき使っているのがエラトステネスのふるいです.
100以下の小数を探します.

1から自分でずっと数字を書きます.

2を除く2の倍数をクリアします.

3以外の3の倍数を取り除きます.

このパージは

4の倍数ですが、2番からパージされ、スキップされました.

ずっと拭きます.

の残りの数字を出力します.

[ 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 ]
これで少数を求めた.

ウィキペディアが提供する画像の説明。

エラトネスのふるいは任意の自然数N以下の少数の方法の中で最も簡単で最も速い方法を探す.

JavaScriptで実現

JavaScriptでエラトステネスの体を実現.

function eratosthenesSieve(array, number) {
  let tempArray = [];

 for (let i = 2; i <= number; i++) {
    tempArray[i] = i;
 }

 for (let i = 2; i <= number; i++) {
   if (tempArray[i] === 0) continue;

   for (let j = i + i; j <= number; j += i) {
     tempArray[j] = 0;
   }
 }

 for (let i = 2; i <= number; i++) {
   if (tempArray[i] !== 0) {
     array.push(tempArray[i]);
   }
 }

  return array;
}

let result = [];
console.log(eratosthenesSieve(result, 100));

まず空の配列temparrayを宣言し、それから2から自分を入れます.
[2,3,4,5,6…98,99,100]

2と3はすでに少数で、2の倍数4から検査を開始します.

4から自分に2を加えて、対応する数字をすべて0にします.

6から自分に3を加えて、対応する数字をすべて0にします.
少数ではないので.

このように自分でもチェックし、小数でない数字をすべてゼロに変更します.

検査終了後
[ 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 ]
これで少数しか残っていない.