language: JavaScript

緒論

特定の数の小数を決定するために関数を実装することを望んでいます.
少数とは何かを理解してみましょう.
「小数」(Prime Number)とは?
1つの大きな自然数のうちの1つと自分だけの数です.
(合成数は1より大きい自然数の非小数であることに注意してください.)
これにより、以下のように少数の条件を定義できます.

1より大きい自然数

1と自分だけがミネラルウォーター

簡単な方法

小数Nは1とそれ自体が約数なので、2からN-1で割ると残りは0ではありません.
これにより、単純な少数の判別関数を作成できます.
数値Nを2からn-1で割った場合、残りの値が0であるかどうかを確認します.

function isPrimeNumber (input) {
  
  if (input <= 1) {
    return false;
  }
  
  for (let i=2; i<input; i++) {
    if (input%i == 0) {
      return false;
    }
  }
  
  return true;
}

時間複雑度O(N)

ショートカット

これは小数判別関数を高速に回転させる方法である.
√√√Nより大きい数は合成数か少数しかありません.(自分でやってみればわかる)
したがって、数字Nを2から√Nで割った場合、残存値が0であるか否かがチェックされる.

function isPrimeNumber (input) {
  
  if (input <= 1) {
    return false;
  }
  
  const sqrt = Math.sqrt(input);
  
  for (let i=2; i<=sqrt; i++) {
    if (input%i == 0) {
      return false;
    }
  }
  
  return true;
}

時間複雑度O(√N)

n/a.結論

特定の数が小数であると判断すると、第2の方法はより速くなります.

+エラトスのふるい

エラトステネスの体説明

は、特定の範囲内で小数を検索する最も速い方法です.

ですが、特定の数が少数かどうかを判断すると、速度が非常に遅くなります.