アルゴリズム|小数を検索-エラトネスの体

4419 ワード
JavaScript アルゴリズム#アルゴリズム# エラトステネスのふるい 小数点を検索 テキストリンク

小数点を検索


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

エラトステネスのふるい


注意:ウィキペディア

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

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

  • 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));
    [BOJ]1463-1 Javaプールの作成
    D - A Simple Problem with Integers