Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 합이 소수가 되는 부분 배열 개수 구하기

문제 개요

양의 정수로 이루어진 배열이 주어집니다. 목표는 연속된 요소들로 이루어진 부분 배열(subarray) 중에서 그 합이 소수(prime)가 되는 경우를 모두 찾아 개수를 세는 것입니다.

예를 들어 배열이 {1, 2, 3, 4}라면, 부분 배열 {1, 2}(합 = 3), {2, 3}(합 = 5), {3, 4}(합 = 7)의 합이 모두 소수이므로 조건을 만족하는 부분 배열의 개수는 3개입니다.

예제 1

입력 − arr[] = {1, 3, 5, 3, 2}

출력 − 합이 소수인 부분 배열의 개수: 3

설명 − 조건을 만족하는 부분 배열은 {3, 2}(합 = 5, 소수), {3, 5, 3}(합 = 11, 소수), {3, 5, 3, 2}(합 = 13, 소수)입니다.

예제 2

입력 − arr[] = {2, 4, 6}

출력 − 합이 소수인 부분 배열의 개수: 0

설명 − 모든 부분 배열의 합이 소수가 아닙니다. 예를 들어 {2, 4} = 6, {4, 6} = 10으로 모두 합성수입니다.

접근 방법

이 프로그램에서 사용하는 접근 방식은 다음과 같습니다.

먼저 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 최댓값 107(천만) 이하의 모든 소수를 미리 구해 vector<bool> 타입의 check 배열에 저장합니다. i가 소수이면 check[i]는 true, 아니면 false가 됩니다. 이후 두 개의 for 루프로 배열을 순회하면서 부분 배열의 합을 누적하고, check[sum] 값을 통해 해당 합이 소수인지 상수 시간에 판별합니다. 소수라면 카운트를 증가시킵니다.

  • 양의 정수 배열 arr[]를 준비합니다.

  • sub_prime(int arr[], int size) 함수는 배열과 크기를 받아 합이 소수인 부분 배열의 개수를 반환합니다.

  • 카운트 변수를 0으로 초기화합니다.

  • temp = pow(10, 7)로 체의 최댓값을 설정합니다.

  • check 벡터를 모두 true로 초기화합니다.

  • 0과 1은 소수가 아니므로 check[0]과 check[1]을 false로 설정합니다.

  • i = 2부터 i * i <= temp까지 반복하면서, i가 소수인 경우 i의 배수들을 모두 false로 표시합니다.

  • 체가 완성되면 check[i]는 i가 소수일 때만 true가 됩니다.

  • 두 개의 for 루프로 배열을 다시 순회합니다.

  • total 변수에 부분 배열 arr[i] ~ arr[j]의 합을 누적합니다. 바깥 루프의 i는 0부터 size - 2까지, 안쪽 루프의 j는 i + 1부터 size - 1까지 진행합니다.

  • check[total]이 true이면(즉, 합이 소수이면) count를 증가시킵니다.

  • 모든 루프가 종료되면 count를 결과로 반환합니다.

C++ 구현 예제

#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

배열 {3, 5, 1, 9, 5}에서 길이가 2 이상인 모든 부분 배열의 합을 계산해 보면, 전체 배열의 합인 3 + 5 + 1 + 9 + 5 = 23만 유일하게 소수이므로 결과는 1이 됩니다.

복잡도 분석

에라토스테네스의 체를 구성하는 데 O(M log log M)(M = 107)의 시간이 걸리고, 부분 배열을 모두 탐색하는 데 O(N²)의 시간이 걸립니다. 공간 복잡도는 체를 저장하기 위해 O(M)입니다. 배열의 크기가 크지 않다면 충분히 실용적인 방법이며, 소수 판별을 매번 나눗셈으로 수행하는 것보다 훨씬 빠릅니다.