C++で2つの配列から素数ペアの合計として得られる一意な値の個数を求める方法

素数と非素数を含む2つの配列が与えられます。この記事の目的は、各配列から素数を取り出してペアを作り、その合計として得られる一意な値の個数を求めることです。

アプローチとしては、両方の配列からそれぞれ素数を選んでペアを作り、その合計を set<int> 型のコンテナに格納していきます。set は重複する値を自動的に排除してくれるため、最終的な set のサイズが「一意な素数の合計の個数」と一致します。

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

入力

Arr1[] = { 1,2,3 } Arr2[] = { 2,3,4}

出力

Distinct Sums of primes :3

説明

素数ペア：(2,2), (2,3), (3,2), (3,3)
一意な合計：4, 5, 6

入力

Arr1[] = { 1,4,6 } Arr2[] = { 2,3,5 }

出力

Distinct Sums of primes :0

説明

Arr1[] には素数が1つも含まれていないため、素数ペアが存在しません。

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

• 正の整数を含む2つの配列 Arr1[] と Arr2[]、およびそれぞれの長さ len1 と len2 を用意します。

• 関数 isprime(int num) は、num が素数であれば 1 を、そうでなければ 0 を返します。

• 関数 prime_Sums(int arr1[], int arr2[], int l1, int l2) は両方の配列を受け取り、素数ペアの合計として得られる一意な値の個数を返します。

• 一意な合計を格納するための set<int> sum を用意します。

• for ループを使って、両方の配列の各要素を走査します。

• isprime(arr1[i]) && isprime(arr2[j]) が真である場合、合計 tmp = arr1[i] + arr2[j] を計算します。

• sum.insert(tmp) によって tmp を set に追加します。重複する値は自動的に無視されます。

• 最後に sum.size() を結果として返します。これが一意な素数の合計の個数です。

例

#include<bits/stdc++.h>
using namespace std;
int isprime(int num){
    if (num <= 1)
        return 0;
    for (int i = 2; i <= num/2; i++)
        if (num % i == 0)
            return 0;
    return 1; // どちらの判定にも引っかからなければ num は素数
}
int prime_Sums(int arr1[],int arr2[],int l1,int l2){
    int count=0;
    set<int> sum;
    for (int i = 0; i < l1; i++){
        for(int j=0; j < l2; j++){
            if(isprime(arr1[i]) && isprime(arr2[j])){
                int tmp=arr1[i]+arr2[j];
                sum.insert(tmp);
            }
        }
    }
    return sum.size();
}
int main(){
    int Arr1[] = { 2, 3, 5 };
    int Arr2[] = { 2, 2, 4, 7 };
    int len1=sizeof(Arr1) / sizeof(Arr1[0]);
    int len2=sizeof(Arr2) / sizeof(Arr2[0]);
    cout<<"Distinct Sums of primes :"<<prime_Sums(Arr1,Arr2,len1,len2);
    return 0;
}

出力

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

Distinct Sums of primes :6

この例では、Arr1 = {2, 3, 5} と Arr2 = {2, 2, 4, 7} から作れる素数ペアの合計は 4, 5, 7, 9, 10, 12 の6種類となるため、答えは 6 になります。なお、素数判定のループ範囲を num/2 ではなく sqrt(num) までにすれば、大きな数に対してもより効率的に処理できます。