C++で指定範囲クエリ内の累積和（プレフィックス合計）に含まれる素数の個数を求める方法

問題概要

この記事では、正の整数からなる配列 arr[ ] と範囲クエリ L、R が与えられたとき、累積和（プレフィックス合計）配列の中に素数がいくつ存在するかを求める方法を解説します。L は累積和の計算を始める配列の開始インデックス arr[L]、R は計算を終えるインデックスです。

累積和配列を作成するには、インデックス L から R まで順番に走査し、元の配列の現在の値に直前の累積和を加えていきます。以下に具体例を示します。

入力 : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
出力 : 3
説明 : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
prefixsum[ ] 配列の 5、11、13 はすべて素数であるため、指定範囲内の素数の個数は 3 となります。

入力 : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
出力 : 1
説明 : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
prefixsum[ ] 配列の中で素数は 29 のみであるため、出力は 1 となります。

解決アプローチ

この問題を解くには、新しい配列 prefixsum[ ] を作成し、直前の累積和に元の配列の現在の要素を加えた値で埋めていきます。累積和配列の最初の要素は、元の配列のインデックス L の値になります。

次に、L から R までの範囲でループを実行して累積和を構築し、prefixsum[ ] 配列の各要素が素数かどうかを判定して、素数が見つかるたびにカウントを増やしていきます。

C++実装例

#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
    vector < bool > p (n);
    bool Prime_val[MAX + 1];
    for (int i = 2; i < MAX; i++)
        Prime_val[i] = true;
    Prime_val[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // Prime_val[p] が true のままなら、p は素数
        if (Prime_val[p] == true){
            // p の倍数をすべて false に更新する
            for (int i = p * 2; i <= MAX; i += p)
                Prime_val[i] = false;
        }
    }
    for (int i = 0; i < n; i++){
        if (Prime_val[arr[i]])
            p[i] = true;
        else
            p[i] = false;
    }
    return p;
}
int main (){
    int arr[] = { 2, 3, 4, 7, 9, 10 };
    int s1 = sizeof (arr) / sizeof (arr[0]); // 与えられた配列のサイズ
    int L = 1, R = 3, s2 = R - L + 1;
    int prefixsum[s2];
    int count = 0;
    prefixsum[0] = arr[L];
    for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
        prefixsum[j] = prefixsum[j - 1] + arr[i];
    }
    vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
    for (int i = 0; i < s2; i++) {
        if (isprime[i] == 1)
            count++;
    }
    cout << "指定範囲クエリにおける累積和の素数の個数: " << count;
    return 0;
}

出力結果

指定範囲クエリにおける累積和の素数の個数: 2

コードの解説

このコードでは、まず prefixsum[ ] 配列を作成し、直前の累積和に元の配列の現在の要素を加えた値で順番に埋めていきます。その後、累積和配列のすべての要素に対して素数判定を行います。素数の判定にはエラトステネスのふるいアルゴリズムを使用しており、これにより複数の値を効率よく一度に判定できます。最後に、素数の数だけカウントを増やし、結果を出力します。

まとめ

この記事では、指定された範囲クエリにおいて累積和に含まれる素数の個数を求める問題を、エラトステネスのふるいを活用して効率的に解く方法を紹介しました。同じロジックは C、Java、Python など他のプログラミング言語でも同様に実装できます。累積和と素数判定を組み合わせた処理は競技プログラミングでも頻出のテクニックなので、ぜひ参考にしてください。この記事が皆さんの学習のお役に立てば幸いです。