【C++】少なくとも1つの要素が素数である配列内のペアの個数を数える方法

問題の概要

正の整数からなる配列が与えられます。この問題の目的は、「少なくとも1つの要素が素数である」異なる要素同士のペアの個数を求めることです。

例えば、配列が [1, 2, 3, 4] の場合、考えられるすべてのペアは (1,2)、(1,3)、(1,4)、(2,3)、(2,4)、(3,4) の6つですが、そのうち少なくとも一方が素数であるのは (1,2)、(1,3)、(2,3)、(2,4)、(3,4) の5つです（1 と 4 は素数ではないため、(1,4) は対象外になります）。

入出力例

入力 − arr[] = { 1, 2, 4, 8, 10 }

出力 − 少なくとも1つの要素が素数であるペアの個数 − 4

説明 − 配列内で唯一の素数は 2 です。2 と他のすべての要素を組み合わせると、(1,2)、(2,4)、(2,8)、(2,10) の4つのペアが得られます。

入力 − arr[] = { 0, 1, 4, 6, 15 }

出力 − 少なくとも1つの要素が素数であるペアの個数 − 0

説明 − 配列に素数が1つも存在しないため、条件を満たすペアはありません。

アルゴリズムのアプローチ

このプログラムでは、エラトステネスの篩の考え方を利用して素数を効率的に判定します。素数・非素数をマークするための補助配列 arr_2[] を作成し、arr_2[i] が 0 なら i は素数、1 なら非素数として扱います。そして、ペア (A, B) について arr_2[A] と arr_2[B] のどちらか一方でも 0 であれば、そのペアをカウント対象とします。

• 正の整数からなる配列 arr[] を用意します。
• 関数 check_prime(int temp, int arr_2[]) は、上限値 temp と配列 arr_2[] を受け取り、各インデックスに対して素数なら 0、非素数なら 1 を設定します。
• 0 と 1 はどちらも素数ではないため、arr_2[0] と arr_2[1] には 1 を設定します。
• 外側の for ループで、i を 2 から i * i <= temp の範囲で走査します。
• 内側のループで、j を 2 * i から開始し、j <= temp の間 j += i ずつ増やしながら、合成数に対して arr_2[j] = 1 を設定します。
• 関数 Prime_Pairs(int arr[], int size) は、配列とそのサイズを受け取り、少なくとも1つの要素が素数であるペアの個数を返します。
• カウント変数 count の初期値を 0 とします。
• temp = *max_element(arr, arr + size) により、配列内の最大値を取得します。
• check_prime(temp, arr_2) を呼び出します。ここで arr_2[] は長さ temp + 1 の配列で、あらかじめ 0 で初期化されています。
• これで、arr_2[i] は i が素数のとき 0、非素数のとき 1 となります。
• 二重の for ループで、i を 0 から size - 1 まで、j を i + 1 から size - 1 まで走査し、すべてのペアを重複なく調べます。
• 各ペア arr[i], arr[j] について、arr_2[arr[i]] == 0 または arr_2[arr[j]] == 0 が成り立てば count をインクリメントします。
• すべてのループが終了したら、count を結果として返します。

実装例（C++）

#include <bits/stdc++.h>
using namespace std;
void check_prime(int temp, int arr_2[]){
   arr_2[0] = 1;
   arr_2[1] = 1;
   for(int i = 2; i * i <= temp; i++){
      if (arr_2[i]==0){
         for (int j = 2 * i; j <= temp; j += i){
            arr_2[j] = 1;
         }
      }
   }
}
int Prime_Pairs(int arr[], int size){
   int count = 0;
   int temp = *max_element(arr, arr + size);
   int arr_2[temp + 1];
   memset(arr_2, 0, sizeof(arr_2));
   check_prime(temp, arr_2);
   for (int i = 0; i < size; i++){
      for (int j = i + 1; j < size; j++){
         if (arr_2[arr[i]] == 0 || arr_2[arr[j]] == 0){
            count++;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 5, 2, 7, 11, 14 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of pairs in an array such that at least one element is prime are: "<<Prime_Pairs(arr, size);
   return 0;
}

出力

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

Count of pairs in an array such that at least one element is prime are: 15

出力結果の解説

この例では、配列 { 3, 5, 2, 7, 11, 14 } のうち素数は 3, 5, 2, 7, 11 の5つで、非素数は 14 のみです。全ペアの総数は C(6,2) = 15 通りであり、両方の要素が非素数であるようなペアは存在しないため、答えは 15 となります。

計算量について

エラトステネスの篩による素数判定の計算量は O(N log log N)（N は配列の最大値）、ペアの全探索は O(n²)（n は配列の要素数）です。したがって、全体の計算量は O(N log log N + n²) となり、各ペアごとに毎回素数判定を行う単純な方法（O(n²√N)）と比べて大幅に効率化できます。特に配列の要素数が多い場合に有効なアプローチです。