すべてのペアの和が素数となる最大の部分集合を求めるC++プログラム

問題概要

与えられた配列の中から、すべてのペアの合計が素数となる最大の部分集合を見つける方法を解説します。ここでは、要素の最大値は100000であると仮定します。まず、以下の例を見てみましょう。

入力: nums[ ] = { 3, 2, 1, 1 }
出力: size = 3, subset = { 2, 1, 1 }
説明:
作成可能な部分集合は {3, 2}、{2, 1}、{2, 1, 1} です。
{2, 1, 1} の場合、ペア (2, 1) の合計は 3 で素数であり、
ペア (1, 1) の合計も 2 で素数となっています。

入力: nums[ ] = {1, 4, 3, 2}
出力: size = 2, subset = {1, 4}
説明:
作成可能な部分集合は {1, 4}、{4, 3}、{3, 2} です。
いずれもサイズが 2 なので、どの部分集合を選んでも構いません。
例えば 1 + 4 = 5 は素数です。

解法へのアプローチ

ペアの合計が素数かどうかを判定する前に、まずその合計が奇数か偶数かを確認する必要があります。2 以外の偶数は素数ではないためです。そして、2つの数の合計が偶数になるのは、両方の数が偶数同士、または奇数同士の場合だけです。

この問題では、x、y、z という3つの数を考えます。このうち任意の2つの数は、偶数同士または奇数同士である必要があります。その上で、この部分集合が素数の合計を持つペアを含むかどうかを確認します。これが成立するのは、以下の2つの場合です。

• 部分集合にいくつかの「1」と、「NUM + 1」が素数となる別の数が含まれている場合。

• または、部分集合に合計が素数となる2つの数のみが含まれている場合。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
#define M 100001
bool check_prime[M] = { 0 };
int sieve_of_eratosthenes(){
    for (int p = 2; p * p < M; p++){
        // マークされていない場合、合成数としてマークする
        if (check_prime[p] == 0){
            // p の倍数をすべて更新
            for (int i = p * 2; i < M; i += p)
                check_prime[i] = 1;
        }
    }
    return 0;
}
int main(){
    sieve_of_eratosthenes();
    int nums[] = { 3, 2, 1, 1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int ones = 0;
    for (int i = 0; i < n; i++)
        if (nums[i] == 1)
            ones++;
    // 「1」が存在し、それ以外の正の要素もある場合
    if (ones > 0){
        for (int i = 0; i < n; i++){
            // nums[i] + 1 が素数かどうかをチェック
            if ((nums[i] != 1) and (check_prime[nums[i] + 1] == 0)){
                cout << ones + 1 << endl;
                // すべての「1」と nums[i] を出力
                for (int j = 0; j < ones; j++)
                    cout << 1 << " ";
                cout << nums[i] << endl;
                return 0;
            }
        }
    }
    // 部分集合に「1」のみが含まれる場合
    if (ones >= 2){
        cout << ones << endl;
        for (int i = 0; i < ones; i++)
            cout << 1 << " ";
        cout << endl;
        return 0;
    }
    // 「1」が存在しない場合
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++){
            // 合計が素数となる整数のペアを探索
            if (check_prime[nums[i] + nums[j]] == 0){
                cout << 2 << endl;
                cout << nums[i] << " " << nums[j] << endl;
                return 0;
            }
        }
    }
// 配列に要素が1つしかない場合
    cout << -1 << endl;
    return 0;
}

出力結果

3
1 1 2

コードの解説

• まず、配列内に含まれる「1」の個数をカウントします。

• 「1」が1つ以上存在する場合は、配列を走査し、「1」以外の各要素について nums[i] + 1 が素数かどうかをチェックします。素数であれば、部分集合のサイズとして (1の個数 + 1) を出力し、その数とすべての「1」を出力します。

• 配列に「1」のみが含まれている場合は、すべてのペアの合計が 2（素数）になるため、すべての「1」を出力します。

• 「1」が1つも存在しない場合は、配列内のすべてのペアを調べ、合計が素数となるペアを探します。

• どの条件にも当てはまらない場合は、-1 を出力します。

まとめ

本記事では、与えられた配列から各ペアの合計が素数となる最大の部分集合を見つける問題について解説しました。エラトステネスの篩（ふるい）を活用して素数を事前に判定し、配列内の「1」の個数に着目することで効率的に解くアプローチを紹介しました。ここで示したC++プログラムのロジックは、C、Java、Python などの他のプログラミング言語でも同様に実装できます。本チュートリアルが皆様の学習のお役に立てば幸いです。