JavaScriptで特定の数までの素数をすべて列挙する方法

はじめに

本記事では、数値 n を受け取り、n 以下に存在するすべての素数を配列として返すJavaScript関数の実装方法を解説します。素数判定のロジックと、それを活用した一括取得の手法を順を追って見ていきましょう。

問題の概要

例えば、入力された数値 n が 24 の場合、期待される出力は以下の通りです。

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

このように、24以下の素数だけを抽出した配列が得られれば成功です。

実装コード

処理は大きく分けて2つの関数で構成します。

• isPrime関数: 引数の数値が素数かどうかを判定するヘルパー関数。2から num / 2 + 1 未満まで順に割り切れるかを確認し、1つでも割り切れる数があれば false を返します。
• primeUpto関数: 指定した数値までの素数を格納した配列を返します。2未満の数値が渡された場合は空配列を返し、初期値として [2] を持った配列に対して、3以降の数値を順番に素数判定しながら追加していきます。

具体的なコードは以下の通りです。

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
]

補足：より効率的な判定について

今回の isPrime 関数は試し割り法を採用しており、判定範囲を num / 2 までに絞ることで計算量を抑えています。さらに効率化したい場合は、判定範囲を √num までに縮めることで、大きな数値に対しても高速に動作させることが可能です。また、大量の素数を一度に求めたいケースでは「エラトステネスのふるい」と呼ばれるアルゴリズムを検討するのも有効です。