C++で「同じ素数の和」として表せる配列要素の個数を数える

正の整数からなるサイズ N の配列 Arr[] が与えられます。この配列の中から、「同じ素数を繰り返し足した和」として表現できる要素の個数を数えるのが本記事の目的です。例えば、4 = 2+2、6 = 3+3 や 2+2+2 のように表せます。

ここで押さえておきたい重要な性質があります。同じ素数どうしの和を考えると、奇素数同士の和(奇数+奇数)であっても、偶数である 2 の和(2+2)であっても、結果は必ず偶数になります。さらに、0 と 2 を除くすべての正の偶数は「2 を繰り返し足す」ことで必ず表せるため(例：8 = 2+2+2+2)、結局「0 でも 2 でもない偶数」だけを数えればよいことになります。

具体例で確認しましょう。

入力

Arr[] = { 2, 5, 10, 15, 20, 25 }

出力

条件を満たす数 : 2

解説

同じ素数の和として表せる数:
Arr[0] = 2  : × count=0
Arr[1] = 5  : × count=0
Arr[2] = 10 : 5+5 → count=1
Arr[3] = 15 : × count=1
Arr[4] = 20 : 5+5+5+5 → count=2
Arr[5] = 25 : × count=2

入力

Arr[] = { 0, 2, 4, 11, 13 }

出力

条件を満たす数 : 1

解説

同じ素数の和として表せる数:
Arr[0] = 0  : × count=0
Arr[1] = 2  : × count=0
Arr[2] = 4  : 2+2 → count=1
Arr[3] = 11 : × count=1
Arr[4] = 13 : × count=1

プログラムで使用しているアプローチ

• 長さ N の正整数配列を受け取ります。

• 関数 sumofparityPrimes(int arr[], int n) が配列と要素数 n を引数に取り、同じ素数の和として表現できる要素の個数を返します。

• カウント用の変数 count を 0 で初期化します。

• for ループで配列を先頭から順に走査します。

• 各要素について、偶数かどうかを調べます(arr[i]%2==0)。

• 偶数であった場合は、それが 0 でも 2 でもないことを確認し、条件を満たしていれば count をインクリメントします。

• for ループ終了後、count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int sumofparityPrimes(int arr[], int n){
    int count = 0;
    for(int i = 0; i < n; i++){
        if(arr[i] % 2 == 0){ // 偶数の場合のみ判定
            if(arr[i] != 0){
                if(arr[i] != 2){
                    count++; // 0 でも 2 でもない偶数
                }
            }
        }
    }
    return count;
}
int main(){
    int Arr[] = { 12, 5, 15, 8, 100, 40 };
    int Length = sizeof(Arr) / sizeof(Arr[0]);
    cout << endl << "条件を満たす数 : " << sumofparityPrimes(Arr, Length);
    return 0;
}

出力

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

条件を満たす数 : 4

計算量について

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(N) です。また、追加のメモリをほとんど使用しないため、空間計算量は O(1) となります。各要素に対して素数判定を繰り返す必要がない点がポイントで、非常にシンプルかつ効率的な解法といえます。