C ++では、合計が素数でn未満のペアをカウントします

入力として正の数nが与えられます。目標は、各ペアが素数でn未満の合計（i + j）を持つように、可能なペア（i、j）の数を見つけることです。また、i！=jおよびi、j> =1 nが4の場合、（1,2）である1つのペアのみが可能です。ここで、1 + 2 =3は素数であり、4未満です。また、1,2>=1です。

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

入力 − n =7

出力 −合計を素数とし、n未満のペアの数は− 3

説明 −ペアは（1,2）、（1,4）、（2,3）になります。合計3、5、5は素数で、7未満です。

入力 − n =10

出力 −合計を素数とし、n未満のペアの数は− 6

説明 −

ペアは（1,2）、（1,4）、（2,3）、（1,6）、（2,5）、（3,4）になります。

合計3、5、5、7、7、7は素数で、10未満です。

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

このアプローチでは、最初に関数check_prime（bool check []、int temp）でSieve of Sundaramを使用して、n未満のすべての素数を見つけます。

また、奇数のtempごとに、合計tempを持つ個別のペアの数はtemp/2になります。

2を除いて、すべての素数は奇数であるため、n未満の素数が見つかった場合は、ペアの数にtemp/2を追加します。

• 変数nを入力として受け取ります。

• 関数prime_pair（int n）はnを取り、合計が素数でn未満のペアの数を返します。

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

• サンダラムのふるいは、入力nに対して2 * n+2未満の素数を生成します。 nを半分に減らし、temp_2に格納します。

• 長さtemp_2の配列Check[]を作成して、フォームのすべての数値（i + j + 2 * i * j）をTrueとしてマークします。すべての要素をfalseとして初期化します。

• 関数check_prime（bool check []、int temp）を使用して、形式の数値（i + j + 2 * i * j）に対してcheck[]をtrueで初期化します。そして、この合計

• 次に、forループを使用してCheck[]をインデックスi=0からi

• 各check[i]がfalseの場合、素数はtemp =2 * i+1になります。

• 合計してtempになるペアはtemp/2になります。

• カウントするためにtemp/2を追加します。

• forループの最後に、合計が素数でn未満の合計ペアがあります。

• 結果としてカウントを返します。

例

#include <bits/stdc++.h>
using namespace std;
void check_prime(bool check[], int temp){
   for (int i=1; i<=temp; i++){
      for (int j=i; (i + j + 2*i*j) <= temp; j++){
         check[i + j + 2*i*j] = true;
      }
   }
}
int prime_pair(int n){
   int count = 0;
   int temp;
   int temp_2 = (n-2)/2;
   bool check[temp_2 + 1];
   memset(check, false, sizeof(check));
   check_prime(check, temp_2);
   for (int i=1; i <= temp_2; i++){
      if (check[i] == false){
         temp = 2*i + 1;
         count += (temp / 2);
      }
   }
   return count;
}
int main(){
   int n = 10;
   cout<<"Count of pairs with sum as a prime number and less than n are: " <<prime_pair(n);
   return 0;
}

出力

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

Count of pairs with sum as a prime number and less than n are: 6