C++で素数の合計を使用してサブ配列をカウントします

正の整数の配列が与えられます。目標は、各サブ配列の合計が素数になるように、配列内の数値のサブ配列を見つけることです。配列が{1,2,3,4}の場合。その場合、サブ配列は{1,2}、{2,3}、{3,4}になります。そのようなサブアレイの数は3です。

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

入力 − arr [] ={1,3,5,3,2};

出力 −プライム合計を持つサブアレイの数は次のとおりです：3

説明 −サブ配列は次のようになります：{3,2} sum =5素数、{3,5,3} sum =11素数、{3,5,3,2}合計は13素数です。

入力 − arr [] ={2,4,6};

出力 −プライムサムを持つサブアレイの数は次のとおりです：0

説明 −すべてのサブアレイには非プライム和があります。 {2,4} =6、{4,6} =10

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

ふるいを使用して最大値107未満のすべての素数を見つけ、vectorチェックに保存します。いずれかの数が素数の場合、check[i]はtrueです。それ以外の場合はfalseです。次に、2つのforループを使用して配列をトラバースし、サブ配列の合計に要素を追加し続け、check[sum]を使用して素数であるかどうかを確認します。はいの場合、プライムサムでサブアレイのカウントをインクリメントします。

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

• 関数sub_prime（int arr []、int size）は配列を受け取り、合計が素数であるサブ配列の数を返します。

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

• temp =pow（10,7）を最大値として初期化します。

• ベクトルチェックをtrueで初期化します。

• check[0]とcheck[1]はプライムではないため、falseです。

• i=2からi*i

• これで、ベクトルcheck [i]は、iが素数の場合はtrue、それ以外の場合はfalseです。

• 2つのforループを使用して配列を再度トラバースします。

• サブアレイ内の要素の合計として変数totalを取ります。 Arr[i]からarr[j]へ。ここで、i=0からi

• check[total]がtrueの場合。 （合計はプライムです）。インクリメントカウント。

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

例

#include <bits/stdc++.h>
using namespace std;
int sub_prime(int arr[], int size){
   int count = 0;
   int temp = int(pow(10, 7));
   vector check(temp + 1, true);
   check[0] = false;
   check[1] = false;
   for (int i = 2; i * i <= temp; i++){
      if (check[i] == true){
         for (int j = i * 2; j <= temp; j += i){
            check[j] = false;
         }
      }
   }
   for (int i = 0; i < size - 1; ++i){
      int total = arr[i];
      for (int j = i + 1; j < size; ++j){
         total += arr[j];
         if (check[total]){
            ++count;
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 3, 5, 1, 9, 5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subarrays with Prime sum are: "<<sub_prime(arr, size);
   return 0;
}

出力

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

Count of subarrays with Prime sum are: 1