C++로 특정 범위 쿼리에서 소수인 접두사 합 개수 구하기

이 글에서는 양의 정수로 이루어진 배열 arr[]와 범위 쿼리 L, R이 주어졌을 때, 접두사 합(prefix sum) 배열 중 소수인 값의 개수를 찾는 방법을 알아봅니다. 여기서 L은 접두사 합 계산을 시작하는 시작 인덱스(arr[L])를 의미하고, R은 처리해야 할 마지막 인덱스를 의미합니다.

접두사 합 배열을 채우려면 인덱스 L부터 R까지 순회하면서 현재 원소의 값을 접두사 합 배열의 이전 원소에 계속 더해 나가면 됩니다. 문제를 이해하기 위한 예시는 다음과 같습니다.

입력 : arr[ ] = { 3, 5, 6, 2, 4 }
L = 1, R = 3
출력 : 3
설명 : prefixsum[ 0 ] = arr[ L ] = 5
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 2 ] = 11
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 3 ] = 13
주어진 범위의 접두사 합 배열에서 5, 11, 13 세 값이 모두 소수입니다.

입력 : arr[ ] = { 6, 10, 5, 8, 11 }
L = 0, R = 3
출력 : 1
설명 : prefixsum[ 0 ] = arr[ L ] = 6
prefixsum[ 1 ] = prefixsum[ 0 ] + arr[ 1 ] = 16
prefixsum[ 2 ] = prefixsum[ 1 ] + arr[ 2 ] = 21
prefixsum[ 3 ] = prefixsum[ 2 ] + arr[ 3 ] = 29
주어진 범위의 접두사 합 배열에서 소수는 29 하나뿐입니다.

해결 접근 방법

문제를 분석해 보면, 먼저 새로운 배열 prefixsum[ ]을 만들고, 접두사 합 배열의 이전 원소와 주어진 배열의 현재 원소를 더한 값으로 이 배열을 채워야 한다는 것을 알 수 있습니다. 접두사 합 배열의 첫 번째 원소는 주어진 배열의 인덱스 L 위치에 있는 값이 됩니다.

그다음, 주어진 배열에서 처리할 인덱스 범위인 L부터 R까지 반복문을 실행하면서 prefixsum[ ] 배열의 각 원소가 소수인지 검사하고, 소수를 발견할 때마다 카운트를 증가시키면 됩니다.

예제 코드

#include<bits/stdc++.h>
using namespace std;
vector < bool > checkprime (int *arr, int n, int MAX){
    vector < bool > p (n);
    bool Prime_val[MAX + 1];
    for (int i = 2; i < MAX; i++)
        Prime_val[i] = true;
        Prime_val[1] = false;
    for (int p = 2; p * p <= MAX; p++){
        // prime[p]가 변경되지 않았다면
        // p는 소수이다
        if (Prime_val[p] == true){
            // p의 모든 배수를 갱신
            for (int i = p * 2; i <= MAX; i += p)
                Prime_val[i] = false;
        }
    }
    for (int i = 0; i < n; i++){
        if (Prime_val[arr[i]])
            p[i] = true;
        else
        p[i] = false;
    }
    return p;
}
int main (){
    int arr[] = { 2, 3, 4, 7, 9, 10 };
    int s1 = sizeof (arr) / sizeof (arr[0]);// 주어진 배열의 크기
    int L = 1, R = 3, s2 = R - L + 1;
    int prefixsum[s2];
    int count = 0;
    prefixsum[0] = arr[L];
    for (int i = L + 1, j = 1; i <= R && j < s1; i++, j++){
        prefixsum[j] = prefixsum[j - 1] + arr[i];

    }
    vector < bool > isprime = checkprime (prefixsum, s2, prefixsum[s2 - 1]);
    for (int i = 0; i < s2; i++) {
        if (isprime[i] == 1)
            count++;
    }
    cout <<"주어진 범위 쿼리에서 소수인 접두사 합의 개수: " << count;
    return 0;
}

실행 결과

주어진 범위 쿼리에서 소수인 접두사 합의 개수: 2

코드 설명

이 코드에서는 먼저 배열 prefixsum[ ]을 생성하고, 접두사 합 배열의 이전 원소와 주어진 배열의 현재 원소를 더한 값으로 배열을 채웁니다. 그런 다음 접두사 합 배열의 모든 값에 대해 소수 여부를 검사하는데, 이때 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 효율적으로 소수를 판별합니다. 마지막으로 소수를 발견할 때마다 카운트를 증가시키고 그 결과를 출력합니다.

결론

이 글에서는 단순 반복 방식과 에라토스테네스의 체를 활용하여, 주어진 범위 쿼리 내에서 소수인 접두사 합의 개수를 구하는 문제를 해결했습니다. 동일한 프로그램은 C, Java, Python 등 다른 프로그래밍 언어로도 작성할 수 있습니다. 이 글이 도움이 되었기를 바랍니다.