小数点を検索

小数を探すのは簡単ですが、時間の複雑さを減らすためには、エラトネスのふるいを使う必要があります.小数点を検索する問題は簡単ですが、リアルタイム符号化でコミットできますので、この点を覚えておいてください.

エラトステネスのふるい

注意:ウィキペディア

エラトネスのふるいは少数を探すために使われている.

アルゴリズム#アルゴリズム#

2から、素数を要求したい区間の全数をリストする.図中の灰色の矩形で囲まれた数はこれに相当する.

2は少数で、右に2と書きます.(赤)
自分以外の2の倍数を消す.

の残りの数の中で、3は少数なので、右側に3と書きます.(緑)
自分以外の3の倍数を消す.

の残りの数のうち、5は少数なので、右に5と書きます.(青)
自分以外の5倍を消す.

の残りの数の中で、7は少数なので、右側に7と書きます.(黄色)
自分以外の7の倍数を消す.

上記の手順を繰り返し、求めた区間の少数の残りをすべて返します.
図中は11 ^ 2 > 120で、11未満の倍数だけ削除すれば十分です.すなわち,120以下の数では,2,3,5,7の倍数を除いて残りは少数である.

ソースコード

const countPrimes = n => {
  const prime = Array(n).fill(true);
  prime[0] = prime[1] = false;

  for (let i = 2; i * i < n; i++) {
    if (prime[i]) {
      for (let j = i * i; j <= n; j += i) {
        prime[j] = false;
      }
    }
  }

  return prime.filter(num => num).length;
};
console.log(countPrimes(10));