C++で合計が素数になる部分配列を数える方法

正の整数からなる配列が与えられたとき、要素の合計が素数になる部分配列（サブ配列）の個数を求めるのが本記事の目的です。例えば、配列 {1, 2, 3, 4} の場合、隣接する要素からなる部分配列 {1,2}、{2,3}、{3,4} の合計はそれぞれ 3・5・7 となり、いずれも素数であるため、条件を満たす部分配列は 3 個となります。

具体的な例で確認してみましょう。

入力 − arr[] = {1, 3, 5, 3, 2}

出力 − 合計が素数になる部分配列の数: 3

説明 − 該当する部分配列は {3, 2}（合計 5）、{3, 5, 3}（合計 11）、{3, 5, 3, 2}（合計 13）の 3 つで、いずれも素数です。

入力 − arr[] = {2, 4, 6}

出力 − 合計が素数になる部分配列の数: 0

説明 − すべての部分配列の合計が素数ではありません。例えば {2, 4} の合計は 6、{4, 6} の合計は 10 です。

プログラムで使用するアプローチ

まず、エラトステネスの篩（ふるい）を用いて最大値 10⁷ までのすべての素数を事前に求め、vector<bool> 型の check に格納します。数 i が素数であれば check[i] は true、そうでなければ false となります。その後、二重の for ループで配列を走査し、部分配列の合計を累積しながら check[sum] を参照して素数かどうかを判定します。素数であればカウントを 1 つ増やします。

• 正の整数からなる配列 arr[] を受け取ります。

• 関数 sub_prime(int arr[], int size) は配列を受け取り、合計が素数になる部分配列の個数を返します。

• カウントの初期値を 0 とします。

• temp = pow(10, 7) を最大値として初期化します。

• vector check を true で初期化します。

• check[0] と check[1] は素数ではないため false に設定します。

• i = 2 から i * i <= temp の間、各 i についてその倍数をすべて false（非素数）としてマークします。

• これにより、check[i] は i が素数のとき true、それ以外は false となります。

• 続いて、二重の for ループで再び配列を走査します。

• 変数 total を部分配列 arr[i] 〜 arr[j] の合計として管理します（i は 0 〜 size-2、j は i+1 〜 size-1）。

• check[total] が true であれば（total が素数であれば）カウントを増やします。

• すべてのループが終わった時点で count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int sub_prime(int arr[], int size){
    int count = 0;
    int temp = int(pow(10, 7));
    vector<bool> check(temp + 1, true);
    check[0] = false;
    check[1] = false;
    for (int i = 2; i * i <= temp; i++){
        if (check[i] == true){
            for (int j = i * 2; j <= temp; j += i){
                check[j] = false;
            }
        }
    }
    for (int i = 0; i < size - 1; ++i){
        int total = arr[i];
        for (int j = i + 1; j < size; ++j){
            total += arr[j];
            if (check[total]){
                ++count;
            }
        }
    }
    return count;
}
int main(){
    int arr[] = { 3, 5, 1, 9, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout<<"合計が素数になる部分配列の数: "<<sub_prime(arr, size);
    return 0;
}

出力

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

合計が素数になる部分配列の数: 1