JavaScript で素数を見つけるアルゴリズムは何ですか?

素数とは、1 とそれ自体でのみ割り切れる正の整数を指します。素数を見つけるアルゴリズムは、コンピューターサイエンスにおける非常に基本的かつ重要な問題であり、暗号化やデータ圧縮などの多くの分野に応用できます。

JavaScript では、素数を見つけるアルゴリズムを実装するのが非常に簡単です。

1. 素数判定法

素数を求める最も基本的な方法であり、原理は正の整数かどうかを判定することです。 1 とそれ自体でのみ割り切れます。

function isPrime(n) {
  if (n <= 1) {
    return false; // 1和0都不是素数
  }

  for (let i = 2; i < n; i++) {
    if (n % i === 0) {
      return false; // 如果n能被i整除，则n不是素数
    }
  }

  return true; // n是素数
}

この関数は正の整数nをパラメータとして受け取り、nが素数の場合はtrueを返し、それ以外の場合はfalseを返します。その時間計算量は O(n) であり、最適ではありません。多数の素数を判定する必要がある場合には、以下で紹介するエラトステネスの篩を使用するのがおすすめです。

2. エラトステネスのふるい

この方法では、一連のふるいを通して合成数を除去し、素数のみを残します。具体的な実装方法は以下の通りです。

function getPrimes(n) {
  let arr = new Array(n + 1).fill(true); // 先创建一个全为 true 的数组，代表是素数
  let primes = [];

  for (let i = 2; i <= n; i++) {
    if (arr[i]) {
      primes.push(i); // i 是素数，添加到 primes 数组中
      for (let j = i * i; j <= n; j += i) {
        arr[j] = false; // 将 i 的倍数都标记为不是素数
      }
    }
  }

  return primes;
}

この関数は正の整数nをパラメータとして受け取り、n以下の素数の配列を返します。計算量はO(n log log n)であり、素数判定法より高速です。

結論

上記は JavaScript で素数を求める 2 つの方法で、実装は単純ですが、非常に実用的です。素数に興味がある場合は、これら 2 つの方法を最適化して、より高速かつ効率的にすることができます。

以上がJavaScript で素数を見つけるアルゴリズムは何ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。