C++ で書かれており、配列内の素数のペアの数を求めます。

この記事では、C を使用して配列内の素数のペアの数を見つける方法についてすべて説明します。整数の配列 arr[] があり、その中に存在する可能性のある素数のペアをすべて見つける必要があります。これが問題の例です -

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

Output : 6

From the given array, prime pairs are
(2, 3), (2, 5), (2, 7), (3, 5), (3, 7), (5, 7)

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

Output : 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]); // size of our array.
    int answer = 0; // counter variable to count the number of prime pairs.
    int MAX = INT_MIN; // Max element
    for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
    }
    bool prime[n]; // boolean array that tells if the element is prime or not.
    memset(prime, false, sizeof(prime)); // initializing all the elements with value of 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

このアプローチでは、各要素が素数かどうかを示すブール配列を作成し、すべての可能なペアを反復処理してチェックします。ペアリング内の 2 つの数値が素数の場合。素数の場合は、答えを 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]); // size of our array.
   int answer = 0; // counter variable to count the number of prime pairs.
   int MAX = INT_MIN; // Max element
   for(int i = 0; i < n; i++){
       MAX = max(MAX, arr[i]);
   }
   bool prime[n]; // boolean array that tells if the element is prime or not.
   memset(prime, false, sizeof(prime)); // initializing all the elements with value of 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 を使用すると、持っている素数のペアの数が計算されます。

上記のコードの説明

このコードでは、エラトステネスのふるいを使用して、大きなバッチになるまですべての素数にラベルを付けます。別のブール配列では、要素が素数であるかどうかをインデックスによってマークします。

最後に、配列全体をループし、存在する素数の総数を見つけ、式 n*(n-1)/2 を使用して考えられるすべての素数のペアを見つけます。この式を使用すると、複雑さは O(N) (N は配列のサイズ) に減ります。

結論

この記事では、O(n) 時間計算量で配列内に存在する素数ペアの数を見つける問題を解決しました。また、この問題を解決する C プログラムと、この問題を解決する完全な方法 (通常かつ効率的) も学びました。同じプログラムを、C、Java、Python などの他の言語で作成できます。

以上がC++ で書かれており、配列内の素数のペアの数を求めます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。