JavaScriptでn番目の素数を効率的に求める方法

本記事では、数値 n を唯一の引数として受け取り、先頭から数えて n 番目の素数 を見つけて返す JavaScript 関数を作成します。

問題の概要

たとえば、n = 6 の場合、素数は「2, 3, 5, 7, 11, 13」の順に並ぶため、出力は 13 になります。

アルゴリズムのポイント

この実装では、以下の工夫によって計算量を抑えています。

• すでに見つけた素数だけを使って素数判定を行う（合成数で割る必要はない）
• 判定対象の平方根まで確認すれば十分という性質を利用する
• 2 以降の候補は奇数のみを順に調べることで無駄な処理を省く

サンプルコード

const findPrime = num => {
    let i, primes = [2, 3], n = 5;
    const isPrime = n => {
        let i = 1, p = primes[i],
        limit = Math.ceil(Math.sqrt(n));
        while (p <= limit) {
            if (n % p === 0) {
                return false;
            }
            i += 1;
            p = primes[i];
        }
        return true;
    }
    for (i = 2; i <= num; i += 1) {
        while (!isPrime(n)) {
            n += 2;
        }
        primes.push(n);
        n += 2;
    };
    return primes[num - 1];
}
console.log(findPrime(6));
console.log(findPrime(16));
console.log(findPrime(66));

コードの解説

• primes 配列：最初の素数 2 と 3 をあらかじめ格納し、以降見つかった素数を順次追加していきます。
• isPrime 関数：既知の素数列を使って割り算を行い、√n 以上の約数を持たなければ素数と判定します。Math.ceil(Math.sqrt(n)) で判定の上限を設定しています。
• メインループ：5 から始めて奇数のみを +2 ずつ調べながら素数を見つけ、配列に追加します。

実行結果

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

13
53
317

このように、findPrime 関数は任意の n に対して正しく n 番目の素数を返します。素数判定を既知の素数だけで行うこのアプローチは、単純な全数チェックよりも効率的で、大きな n に対しても実用的な速度で動作します。