【C++】Nより大きいK番目の素数を求めるアルゴリズムと実装方法

はじめに

このチュートリアルでは、C++を使って「与えられた数 n より大きい k 番目の素数」を求めるプログラムを作成します。たとえば n = 5、k = 23 の場合、5より大きい素数を小さい順に数えて23番目となる 101 が出力されます。

アルゴリズム

この問題は、あらかじめ素数表を作成しておくことで効率的に解けます。手順は以下の通りです。

• 数 n を初期化します。
• エラトステネスの篩を用いて、10⁶(1,000,000)までのすべての素数を求め、bool型の配列に格納します。
• n + 1 から 10⁶ まで順に走査するループを作成します。
  • 現在の数が素数であれば、カウンタ k を1減らします。
  • k が0になった時点で、その数を答えとして返します。
• 範囲内に見つからなかった場合は -1 を返します。

プログラム例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 1e6;
bool prime[MAX_SIZE + 1];

void findAllPrimes() {
    memset(prime, true, sizeof(prime));
    for (int p = 2; p * p <= MAX_SIZE; p++) {
        if (prime[p]) {
            for (int i = p * p; i <= MAX_SIZE; i += p) {
                prime[i] = false;
            }
        }
    }
}

int findKthPrimeGreaterThanN(int n, int k) {
    for (int i = n + 1; i < MAX_SIZE; i++) {
        if (prime[i]) {
            k--;
        }
        if (k == 0) {
            return i;
        }
    }
    return -1;
}

int main() {
    findAllPrimes();
    int n = 5, k = 23;
    cout << findKthPrimeGreaterThanN(n, k) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次の出力が得られます。

101

コードの解説

findAllPrimes() 関数では、エラトステネスの篩を実装しています。まず配列全体を true で初期化し、2から順に各素数の倍数をふるい落としていくことで素数表を完成させます。計算量は O(N log log N) と非常に高速です。

findKthPrimeGreaterThanN() 関数では、n + 1 以降の数を順にチェックし、素数が見つかるたびに k を減算していきます。k が0になった時点の値が、求める「nより大きいk番目の素数」です。このように前処理で素数表を作っておけば、同じようなクエリを何度も処理する場合にも高速に対応できます。

まとめ

このチュートリアルでは、エラトステネスの篩による前処理を活用して、nより大きいk番目の素数を効率よく求める方法を学びました。本チュートリアルについて質問がある場合は、コメント欄でお知らせください。