C++で部分配列に含まれる素数の個数を効率的に求める方法

本記事では、部分配列（サブアレイ）内に含まれる素数の個数を求める方法を解説します。正の整数からなる配列 arr[] と、範囲 {L, R} を指定する q 個のクエリが与えられ、それぞれのクエリに対して指定された範囲内に存在する素数の個数を出力する必要があります。

まず、問題の具体例を見てみましょう。

入力：arr[] = {1, 2, 3, 4, 5, 6}、q = 1、L = 0、R = 3
出力：2
指定された範囲内の素数は {2, 3} の2個です。

入力：arr[] = {2, 3, 5, 8, 12, 11}、q = 1、L = 0、R = 5
出力：4
指定された範囲内の素数は {2, 3, 5, 11} の4個です。

解決アプローチ

この問題に対して、主に以下の2つのアプローチが考えられます。

1. 総当たり（ブルートフォース）法

最も単純な方法は、指定された範囲内の各要素について素数判定を行い、その個数を数えることです。

実装例

#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
    if (N <= 1)
        return false;
    if (N <= 3)
        return true;
    if(N % 2 == 0 || N % 3 == 0)
        return false;
    for (int i = 5; i * i <= N; i = i + 2){ // 偶数は素数になり得ないため、i を2ずつ増加させる
        if (N % i == 0)
            return false; // いずれかの数で割り切れるなら素数ではない
    }
    return true;
}
int main(){
    int N = 6; // 配列のサイズ
    int arr[N] = {1, 2, 3, 4, 5, 6};
    int Q = 1;
    while(Q--){
        int L = 0, R = 3;
        int cnt = 0;
        for(int i = L; i <= R; i++){
            if(isPrime(arr[i]))
                cnt++; // カウンタ変数
        }
        cout << cnt << "\n";
    }
    return 0;
}

出力結果

2

しかし、この方法は全体の計算量が O(Q×N×√N) となり、クエリ数や配列サイズが大きくなると非常に非効率です。

2. 効率的なアプローチ（エラトステネスの篩）

そこで有効なのが「エラトステネスの篩」です。あらかじめブール型の配列を作成し、各要素が素数かどうかをフラグとして記録しておきます。その後、クエリごとに指定された範囲を走査し、フラグを参照するだけで素数の総数を求められます。

実装例

#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
    vector<bool> p(n);
    bool Prime[MAX + 1];
    for(int i = 2; i < MAX; i++)
        Prime[i] = true;
    Prime[1] = false;
    for (int p = 2; p * p <= MAX; p++) {
        // Prime[p] が true のままなら p は素数
        if (Prime[p] == true) {
            // p の倍数をすべて合成数としてマーク
            for (int i = p * 2; i <= MAX; i += p)
                Prime[i] = false;
        }
    }
    for(int i = 0; i < n; i++){
        if(Prime[arr[i]])
            p[i] = true;
        else
            p[i] = false;
    }
    return p;
}
int main(){
    int n = 6;
    int arr[n] = {1, 2, 3, 4, 5, 6};
    int MAX = -1;
    for(int i = 0; i < n; i++){
        MAX = max(MAX, arr[i]);
    }
    vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // ブール型配列
    int q = 1;
    while(q--){
        int L = 0, R = 3;
        int cnt = 0; // カウント
        for(int i = L; i <= R; i++){
            if(isprime[i])
                cnt++;
        }
        cout << cnt << "\n";
    }
    return 0;
}

出力結果

2

コードの解説

このアプローチでは、事前に各要素が素数であるかどうかを判定してフラグ付けしておくため、クエリ処理時の計算量は O(Q×N) となり、先ほどの総当たり法よりも大幅に高速化できます。

さらに、エラトステネスの篩を用いることで、素数判定そのものも高速に行えます。この手法では、各数値をその素因数を使ってマークしていくことで、O(N・log(log(N))) の計算量ですべての数値の素数判定を完了させることができます。

まとめ

本記事では、エラトステネスの篩を活用して、部分配列内の素数の個数を O(Q×N) で求める問題を解説しました。総当たり法と効率的な手法の両方のC++プログラムと実装の考え方を紹介しましたので、ぜひ参考にしてください。なお、同じロジックはC言語、Java、Pythonなど他のプログラミング言語でも同様に実装可能です。