エラトステネスのふるいを使ってJavaScriptで素数を求める方法

JavaScriptで、ある数値 n を受け取る関数を作成する必要があります。

この関数は、1から n までの間に存在するすべての素数を配列として返します。

アルゴリズムの考え方

まず、与えられた数値と同じ大きさの配列を作成し、すべての値を true で初期化します。この配列のインデックスが「素数の候補」を表し、最初はすべてが素数候補（true）であるという状態になります。

次に、2から与えられた数値の平方根まで繰り返す for ループを作成します。合成数（整数の積）は定義上素数になり得ないため、各 i の倍数にあたるインデックスを false に設定していきます。0 と 1 は、それらで割り切れるかどうかは素数判定に影響しないため、あらかじめ除外しておきます。

最後に、false の値をすべて除外すれば、残ったものが求める素数のリストとなります。

コード例

const num = 100;
const findPrimes = (num = 10) => {
    const numArr = new Array(num + 1);
    numArr.fill(true);
    numArr[0] = numArr[1] = false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        for (let j = 2; i * j <= num; j++){
            numArr[i * j] = false;
        }
    }
    return numArr.reduce((acc, val, ind) => {
        if(val){
            return acc.concat(ind);
        }else{
            return acc;
        };
    },[]);
};
console.log(findPrimes(num));

出力結果

コンソールには以下のように出力されます。

[
    2, 3, 5, 7, 11, 13, 17, 19,
    23, 29, 31, 37, 41, 43, 47, 53,
    59, 61, 67, 71, 73, 79, 83, 89,
    97
]

処理のポイント

このアルゴリズムでは、内側のループの上限を「与えられた数値の平方根」までとしている点が重要です。ある数が合成数であれば、必ずその平方根以下の約数を持つため、平方根まで調べれば十分に素数判定が完了します。これにより、全ての数を個別に判定する方法と比べて計算量を大幅に削減でき、効率的に素数を列挙できます。