コード戦争に時間を費やしたことがある場合、数が素数であるかどうかを見つけることは、問題のカテゴリの中で共通のテーマです。 私が最初にコーディングを始めたとき、私はすべての数字1からnumまでループし、それが割り切れるかどうかを確認することは素晴らしいアプロー しかし、すぐに私はビッグO記法について学んだとして、私は悔しかったです!今週末にいくつかの研究とwikiを読んだ後、私は数が部分線形O(n)時間で素数であるかどうかを見つけるための素晴らしい関数を見つけました。 次の機能は私が見つけた解決策です:

function isPrime (num) {
if (num <= 1) {
return true
} else if (num <= 3) {
return true
} else if (num%2 === 0 || num%3 === 0) {
return false
}
let i = 5
while (i*i <= num) {
if (num%i === 0 || num%(i+2) === 0) {
return false
}
i += 6
}
return true
}
  1. 数値が0、1、または負の値であるかどうかを確認します。 数値がこの範囲内の場合はtrueを返します。
  2. は、数字が2か3かをチェックします。 数値が2または3の場合はtrueを返します。
  3. 最後のifステートメントは、2または3で割り切れる場合、数値が素数ではないことを返します。
  4. この関数の最後の部分は最もトリッキーです—whileループ! 基本的には、numの平方根よりも大きくなるまで、3で割り切れないすべての奇数をチェックしています。 たとえば、最初のii + 2は5と7になります。 次のii + 2は11と13になります。 両方とも3で割り切れるため、9または15はチェックされず、最後のelse ifステートメントでキャッチされています。
  5. は、数値が素数であるためにiまたはi+2エントリで割り切れなかった場合、最後にtrueを返します。NがisPrimeに渡された数であると仮定すると、私の最初のアプローチのO(n)はO(n)になります。 したがって、この時間の複雑さは線形になります。 あなたがしていることがチェックだけであればこれは問題ありませんが、この関数は何度もヘルパー関数であり、数字のリストが素数であるかどうか上記の関数isPrimeはO(n^1/2)になります。 これは、時間の複雑さが副線形になり、より大きな関数の時間の複雑さが大幅に減少することを意味します。