C++で配列内の素数ペアの個数を効率的に求める方法

この記事では、C++を使って配列内に存在する素数ペアの個数を求める方法について、基礎から応用まで詳しく解説します。整数型の配列 arr[] が与えられ、その中から作れるすべての素数ペアを数えるのが目的です。

まず、問題の具体例を見てみましょう。

入力 : arr[ ] = { 1, 2, 3, 5, 7, 9 }

出力 : 6

配列から作れる素数ペアは以下の6通り
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)

入力 : arr[] = {1, 4, 5, 9, 11}

出力 : 1

解法のアプローチ

総当たり（ブルートフォース）法

最初に紹介するのは、最も基本的な総当たり法です。ただしこの方法は計算効率が良くないため、後ほどより高速な手法も併せて紹介します。

実装例

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
    bool p[MAX+1];
    memset(p, true, sizeof(p));
    p[1] = false;
    p[0] = false;
     for(int i = 2; i * i <= MAX; i++){
        if(p[i] == true){
            for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
            }
        }
    }
    for(int i = 0; i < n; i++){
        if(p[arr[i]] == true)
           prime[i] = true;
    }
}
int main(){
    int arr[] = {1, 2, 3, 5, 7, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int answer = 0; // 素数ペアの個数を数えるカウンタ変数
    int MAX = INT_MIN; // 配列内の最大値
    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // 各要素が素数かどうかを示すbool型配列
    memset(prime, false, sizeof(prime)); // すべてfalseで初期化
    seiveOfEratosthenes(arr, prime, n, MAX);
    for(int i = 0; i < n-1; i++){
        for(int j = i+1; j < n; j++){
            if(prime[i] == true && prime[j] == true)
               answer++;
         }
    }
    cout << answer << "\n";
    return 0;
}

実行結果

6

このアプローチでは、まず各要素が素数かどうかを判定するためのbool型配列を作成します。その後、考えられるすべてのペアを順番に調べ、ペア内の両方の数が素数であれば答えを1ずつ加算していきます。

しかし、この方法の時間計算量は O(N×N)（Nは配列のサイズ）となるため、大規模なデータには不向きです。次に、この処理を高速化する方法を見ていきましょう。

効率的なアプローチ

こちらのアプローチでは、コードの大部分は前述の方法と同じですが、重要な変更点として、すべてのペアを実際に調べる代わりに、数学の公式を使ってペアの個数を直接計算します。

実装例

#include <bits/stdc++.h>
using namespace std;
void seiveOfEratosthenes(int *arr, bool *prime, int n, int MAX){
   bool p[MAX+1];
   memset(p, true, sizeof(p));
   p[1] = false;
   p[0] = false;
   for(int i = 2; i * i <= MAX; i++){
       if(p[i] == true){
           for(int j = i*2; j <= MAX; j += i){
               p[j] = false;
           }
       }
    }
    for(int i = 0; i < n; i++){
       if(p[arr[i]] == true)
           prime[i] = true;
   }
}
int main(){
   int arr[] = {1, 2, 3, 5, 7, 8, 9};
   int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
   int answer = 0; // 素数ペアの個数を数えるカウンタ変数
   int MAX = INT_MIN; // 配列内の最大値
   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // 各要素が素数かどうかを示すbool型配列
   memset(prime, false, sizeof(prime)); // すべてfalseで初期化
   seiveOfEratosthenes(arr, prime, n, MAX);
   for(int i = 0; i < n; i++){
       if(prime[i] == true)
           answer++;
   }
   answer = (answer * (answer - 1)) / 2;
   cout << answer << "\n";
   return 0;
}

実行結果

6

ご覧のとおり、コードの大部分は前のアプローチと共通ですが、計算量を大幅に削減している关键となるのが、使用した公式 n(n-1)/2 です。この公式により、素数ペアの個数を一発で算出できます。

コードの解説

このコードでは、エラトステネスの篩（ふるい） を使って、配列内の最大要素までのすべての素数をマークしています。さらに別のbool型配列を用意し、元の配列の各インデックスに対応する要素が素数かどうかを記録します。

最後に配列全体を走査して素数の総数を求め、公式 n×(n-1)/2 を適用することで、作成可能なすべてのペアの個数を導き出します。この公式のおかげで、時間計算量は O(N)（Nは配列のサイズ）まで削減されます。

まとめ

この記事では、配列内に存在する素数ペアの個数を O(n) の時間計算量で求める問題を解説しました。通常の総当たり法と、公式を活用した効率的な手法の両方のC++プログラムと実装の考え方を学びました。同様のプログラムは、C、Java、Pythonなど他のプログラミング言語でも実装可能です。