【JavaScript】n以下の素数をすべて配列で取得する方法

本記事では、数値 n を引数として受け取り、n 以下のすべての素数を格納した配列を返す JavaScript 関数の作成方法を解説します。

たとえば、n が 24 の場合、期待される出力は次のとおりです。

const output = [2, 3, 5, 7, 11, 13, 17, 19, 23];

実装の考え方

この処理は、次の2つのステップで構成されます。

1. 素数判定用の補助関数（isPrime）：ある数が素数かどうかを判定する。2 から順に割り算を行い、途中で割り切れる数が現れた時点で素数ではないと判断します。
2. メイン関数（primeUpto）：3 から n までの各整数に対して isPrime を呼び出し、素数であれば結果配列へ追加していきます。

なお、判定処理では「num / 2 + 1」未満の数でのみ割り算を試すことで、無駄な計算を減らしています。

コード例

実際のコードは以下のとおりです。

const num = 24;
const isPrime = num => {
   let count = 2;
   while(count < (num / 2)+1){
      if(num % count !== 0){
         count++;
         continue;
      };
      return false;
   };
   return true;
};
const primeUpto = num => {
   if(num < 2){
      return [];
   };
   const res = [2];
   for(let i = 3; i <= num; i++){
      if(!isPrime(i)){
         continue;
      };
      res.push(i);
   };
   return res;
};
console.log(primeUpto(num));

出力結果

上記のコードを実行すると、コンソールには次のように出力されます。

[
   2,  3,  5,  7, 11,
   13, 17, 19, 23
]

パフォーマンスをさらに高めるポイント

より大きな数値を扱う場合は、素数判定の範囲を「num / 2」ではなく √num（平方根）までに絞ると、計算量を大幅に削減できます。また、エラトステネスのふるいを使えば、n までの素数をより効率的に一括取得することも可能です。