JavaScriptで指定した範囲内の素数の個数を求める方法

問題の概要

今回は、2つの数値（a と b）を受け取り、その間に存在する素数の総数を返す JavaScript 関数を作成します。a と b 自体が素数である場合は、それらもカウントに含めます。

例を見てみましょう。

a = 2、b = 21 の場合、
この範囲内の素数は 2, 3, 5, 7, 11, 13, 17, 19 の8個

この場合、関数は 8 を返す必要があります。

実装の考え方

まず、ある数が素数かどうかを判定する補助関数 isPrime() を用意します。判定には、2 から num/2+1 未満までの整数で順番に割り切れるかを確認する方法を使います。1つでも割り切れる数があれば素数ではないと判断し、false を返します。

次に、メインとなる関数 primeBetween() では、Math.min() と Math.max() を使って引数の大小関係に関係なく正しい範囲を設定し、範囲内の各数値に対して isPrime() を呼び出してカウントを集計します。

サンプルコード

const isPrime = num => {
    let count = 2;
    while(count < (num / 2)+1){
        if(num % count !== 0){
            count++;
            continue;
        };
        return false;
    };
    return true;
};
const primeBetween = (a, b) => {
    let count = 0;
    for(let i = Math.min(a, b); i <= Math.max(a, b); i++){
        if(isPrime(i)){
            count++;
        };
    };
    return count;
};
console.log(primeBetween(2, 21));

実行結果

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

8

コードの解説

• isPrime 関数： 2 から始まる除数で割り切れるかどうかを順にチェックします。num の半分を超える約数は存在しないため、(num / 2) + 1 まで調べれば十分です。
• primeBetween 関数： 引数として渡された a と b の大小がどちらであっても動作するよう、Math.min() と Math.max() で範囲の開始・終了を決めています。

パフォーマンスに関する補足

上記の実装はシンプルで分かりやすい反面、大きな数値範囲では処理が遅くなる可能性があります。より効率化したい場合は、以下のような改善策が有効です。

• 平方根まで判定する： 素数判定では num の平方根以下の数だけ調べればよいため、ループ条件を count <= Math.sqrt(num) に変更できます。
• エラトステネスのふるい： 広い範囲の素数を一括で求める場合、このアルゴリズムを使うと大幅に高速化できます。