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입니다. 그런 다음 두 개의 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
이제 i가 소수이면 벡터 검사[i]가 true이고 그렇지 않으면 false입니다.
두 개의 for 루프를 사용하여 배열을 다시 탐색합니다.
변수 total을 하위 배열의 요소 합으로 가져옵니다. Arr[i]에서 arr[j]로. 여기서 i=0 ~ i
체크[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