少なくとも1つの要素がC++で素数になるように、配列内のペアをカウントします

正の整数の配列が与えられます。目標は、少なくとも1つのプライムメンバーを持つ配列の要素の個別のペアの数を見つけることです。配列が[1,2,3,4]の場合、ペアは（1,2）、（1,3）、（2,3）、（2,4）、および（3,4）になります。

例を挙げて理解しましょう

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

出力 −少なくとも1つの要素が素数であるような配列内のペアの数は− 4

説明 −唯一の素元は2であり、それを他のすべてと組み合わせると、−（1,2）、（2,4）、（2,8）、（2,10）が得られます。

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

出力 −少なくとも1つの要素が素数であるような配列内のペアの数は− 0

説明 −配列には素元がありません。

以下のプログラムで使用されているアプローチは次のとおりです

素数と非素数をマークするための配列arr_2[]を作成します。 arr_2 [i]が0の場合、iは素数であり、それ以外の場合は非素数です。いずれかのペアについて、任意の値arr_2 [A]、arr_2 [B]が0の場合、ペア（A、B）がカウントされます。

• 正の整数の配列arr[]を取ります。

• 関数check_prime（int temp、int arr_2 []は、値tempを最高として、配列arr_2 []を取り、arr_2[]に素数としてのインデックスとして0を設定します。

• 0と1の両方が非素数であるため、arr_2 [0] =arr_2 [1]=0に設定します。

• ここでforループを使用して、i=2からi*iまでトラバースします。

• j =2*iからj<=tempおよびj+=iにトラバースします。非素数の場合はarr_2[j]=1に設定します。

• 関数Prime_Pairs（int arr []、int size）は、配列とそのサイズを受け取り、少なくとも1つの要素が素数であるペアの数を返します。

• 初期カウントを0とします。

• 配列間の最大値としてtemp=* max_element（arr、arr + size）を初期化します。

• check_prime（temp、arr_2）を呼び出します。ここで、arr_2 []は0で初期化され、長さはtempです。

• これで、arr_2 []が作成されます。ここで、arr [i]は、素数としてiの場合は0、非素数としてiの場合は1です。

• i=0からi

• 各ペアarr[i]について、arr[j]はarr_2[arr [i]]==0またはarr_2[arr[j]]==0かどうかを確認します。はいの場合はカウントをインクリメントします。

• 結果として、すべてのループの終了時にカウントを返します。

例

#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