【JavaScript】2からnまでの素数の個数を数える関数の実装方法

問題の概要

本記事では、数値 n を唯一の引数として受け取り、2 から n までの範囲に含まれる素数の個数を返す JavaScript 関数の実装方法を解説します。

入出力の例

n = 10 の場合 → 出力は 4（素数： 2, 3, 5, 7）
n = 1 の場合 → 出力は 0

実装コード

以下のコードは、古典的なアルゴリズム「エラトステネスの篩（ふるい）」の考え方を応用したものです。配列を使って合成数を順に除外していくことで、効率よく素数を数えています。

const countPrimesUpto = (num = 1) => {
    if (num < 3) {
        return 0;
    }

    // 全要素を 1（素数候補）で初期化
    let arr = new Array(num).fill(1);

    // i の平方根まで調べれば十分
    for (let i = 2; i * i < num; i++) {
        if (!arr[i]) {
            continue;
        }

        // i の倍数を合成数としてマーク（0 にする）
        for (let j = i * i; j < num; j += i) {
            arr[j] = 0;
        }
    }

    // 残った 1 の合計から、0 と 1 の分（2 つ）を差し引く
    return arr.reduce((a, b) => b + a) - 2;
};

console.log(countPrimesUpto(35));
console.log(countPrimesUpto(6));
console.log(countPrimesUpto(10));

コードの解説

• 初期チェック： num が 3 未満の場合は 2 以上の素数が存在しないため、0 を返します。
• 配列の準備： 長さ num の配列を作成し、全要素を 1 で埋めます。1 は「まだ素数候補である」ことを表します。
• ふるい処理： i を 2 から順に確認し、i が素数のまま残っていれば、i*i から始めて i の倍数をすべて 0（合成数）にマークします。i*i 未満の倍数は、より小さい素数の段階ですでに処理済みのため、開始点を i*i としても問題ありません。
• 集計： 最後に配列内の 1 の総和を求め、インデックス 0 と 1 の分にあたる 2 を引くことで、素数の個数が得られます。

出力結果

コンソールには次のように表示されます。

11
3
4

countPrimesUpto(35) は 35 未満に 11 個の素数、countPrimesUpto(6) は 3 個（2, 3, 5）、countPrimesUpto(10) は 4 個（2, 3, 5, 7）という結果です。

まとめ

この手法の計算量は O(n log log n) と非常に効率的で、それぞれの数について割り算を試す単純な方法（O(n√n)）よりも大幅に高速です。大きな n に対して素数の個数を求めたい場合に特に有効なアプローチなので、ぜひ活用してみてください。