JavaScriptで指定した範囲内からランダムな素数を生成する方法

本記事では、2つの数値で範囲を指定して受け取り、その範囲内に存在するランダムな素数を返すJavaScript関数の実装方法を解説します。

全体のアプローチ

処理の流れは以下の3ステップです。

1. 指定された範囲（min〜max）内のすべての素数を抽出する
2. 抽出した素数リストから、ランダムなインデックスを使って1つを選ぶ
3. 選ばれた素数を返す

素数の抽出には、エラトステネスの篩の考え方を応用します。配列に対して合成数（素数以外の数）を順番に削除していき、残った値だけが素数になる仕組みです。

コード例

const range = [100, 1000];

// 範囲内の素数をすべて取得する関数
const getPrimes = (min, max) => {
   const result = Array(max + 1)
   .fill(0)
   .map((_, i) => i);
   // 合成数を削除していく（エラトステネスの篩）
   for (let i = 2; i <= Math.sqrt(max + 1); i++) {
      for (let j = i ** 2; j < max + 1; j += i) delete result[j];
   }
   return Object.values(result.slice(min));
};

// min〜max の間のランダムな整数を返す関数
const getRandomNum = (min, max) => {
   return Math.floor(Math.random() * (max − min + 1) + min);
};

// 素数リストからランダムに1つ選んで返す関数
const getRandomPrime = ([min, max]) => {
   const primes = getPrimes(min, max);
   return primes[getRandomNum(0, primes.length − 1)];
};

console.log(getRandomPrime(range));

コードの解説

getPrimes関数

まず、0からmaxまでの連続した数値を持つ配列を生成し、2から√(max+1)までの各数値について、その倍数（平方数以降）を順次削除していきます。これにより、範囲内の素数だけが残り、Object.values()によって配列として返されます。

getRandomNum関数

Math.random()とMath.floor()を組み合わせることで、min以上max以下のランダムな整数を生成します。(max − min + 1)を掛けることで範囲の幅を表現し、minを加算することで下限を調整しています。

getRandomPrime関数

引数として受け取った範囲配列を分割代入で展開し、getPrimesで素数リストを取得した後、リスト長を上限としたランダムインデックスで1つの素数を取り出して返します。

出力結果

311

このコードではMath.random()を使用しているため、実行するたびに出力される値は変化します。上記の出力はあくまで一例です。