JavaScriptで指定した数より大きい最小の素数を見つける方法

問題

JavaScriptで、ある数値 n を受け取る関数を作成することを考えます。この関数は、n より大きい数の中で最小となる素数を返す必要があります。

アプローチ

まず、与えられた数が素数かどうかを判定する補助関数 isPrime を用意します。素数判定では、2 からその数の平方根まで順に割り切れるかを確認すれば十分です。平方根以降の因数は必ずペアが存在するため、ここまで調べれば判定できます。これにより計算量を大幅に抑えられます。

次に、nextPrime 関数の中で、引数の数値を1ずつ増やしながら isPrime で判定を行い、最初に見つかった素数を返します。

コード例

以下が実際のコードです。

const num = 101;
const isPrime = (num) => {
   let sqrtnum = Math.floor(Math.sqrt(num));
   let prime = num !== 1;
   for(let i = 2; i < sqrtnum + 1; i++){
      if(num % i === 0){
         prime = false;
         break;
      };
   };
   return prime;
}
const nextPrime = (num = 1) => {
   while(!isPrime(++num)){
   };
   return num;
};
console.log(nextPrime(num));

コードの解説

isPrime 関数では、まず Math.sqrt を使って入力値の平方根を求め、小数点以下を切り捨てています。初期値として prime = num !== 1 を設定することで、1 は素数ではないことが自動的に処理されます。ループ内で一度でも割り切れる数が見つかれば即座に false を返して処理を終了します。

nextPrime 関数では、前置インクリメント演算子 ++num を使って数値を先に1増やしてから素数判定を行っています。これにより、元の数値自体ではなく「その次」から探索が始まります。

出力

上記のコードを実行すると、コンソールには以下の結果が出力されます。

103

101 の次に現れる素数は 102 ではなく 103（101 と 104 の間で唯一の素数）であるため、正しく動作していることがわかります。