문제 소개
이 글에서는 부분 배열(subarray)에 포함된 소수의 개수를 구하는 방법을 알아봅니다. 양의 정수로 이루어진 배열 arr[]와 두 개의 정수로 범위 {L, R}를 나타내는 q개의 쿼리가 주어졌을 때, 해당 범위 안에 있는 소수가 몇 개인지 구하는 것이 목표입니다.
아래는 문제의 예시입니다.
입력 : arr[] = {1, 2, 3, 4, 5, 6}, q = 1, L = 0, R = 3
출력 : 2
주어진 범위에서 소수는 {2, 3}입니다.
입력 : arr[] = {2, 3, 5, 8, 12, 11}, q = 1, L = 0, R = 5
출력 : 4
주어진 범위에서 소수는 {2, 3, 5, 11}입니다.해결 접근 방식
이 문제를 해결하기 위해 크게 두 가지 방법을 생각해 볼 수 있습니다.
1. 브루트 포스(Brute Force)
가장 단순한 방법은 주어진 범위를 하나씩 순회하면서 각 원소가 소수인지 직접 판별하는 것입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
bool isPrime(int N){
if (N <= 1)
return false;
if (N <= 3)
return true;
if(N % 2 == 0 || N % 3 == 0)
return false;
for (int i = 5; i * i <= N; i = i + 2){ // 짝수는 소수가 될 수 없으므로 i를 2씩 증가시킵니다.
if (N % i == 0)
return false; // N이 어떤 수로 나누어떨어지면 소수가 아닙니다.
}
return true;
}
int main(){
int N = 6; // 배열의 크기
int arr[N] = {1, 2, 3, 4, 5, 6};
int Q = 1;
while(Q--){
int L = 0, R = 3;
int cnt = 0;
for(int i = L; i <= R; i++){
if(isPrime(arr[i]))
cnt++; // 카운터 변수
}
cout << cnt << "\n";
}
return 0;
}
실행 결과
2
하지만 이 방법은 그다지 좋지 않습니다. 쿼리마다 범위 전체를 탐색하고, 각 원소마다 제곱근까지 나눗셈 검사를 반복하기 때문에 전체 시간 복잡도가 O(Q*N*√N)에 달합니다. 데이터가 커지면 성능이 급격히 저하됩니다.
2. 효율적인 접근: 에라토스테네스의 체(Sieve of Eratosthenes)
더 나은 성능을 위해서는 에라토스테네스의 체를 활용할 수 있습니다. 미리 불리언(bool) 배열을 만들어 각 원소가 소수인지 여부를 표시해 둔 뒤, 쿼리가 들어올 때마다 해당 범위만 순회하며 소수 개수를 세면 됩니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
vector<bool> sieveOfEratosthenes(int *arr, int n, int MAX){
vector<bool> p(n);
bool Prime[MAX + 1];
for(int i = 2; i < MAX; i++)
Prime[i] = true;
Prime[1] = false;
for (int p = 2; p * p <= MAX; p++) {
// Prime[p]가 변경되지 않았다면 p는 소수입니다.
if (Prime[p] == true) {
// p의 모든 배수를 소수가 아니라고 표시합니다.
for (int i = p * 2; i <= MAX; i += p)
Prime[i] = false;
}
}
for(int i = 0; i < n; i++){
if(Prime[arr[i]])
p[i] = true;
else
p[i] = false;
}
return p;
}
int main(){
int n = 6;
int arr[n] = {1, 2, 3, 4, 5, 6};
int MAX = -1;
for(int i = 0; i < n; i++){
MAX = max(MAX, arr[i]); // 배열의 최댓값을 구합니다.
}
vector<bool> isprime = sieveOfEratosthenes(arr, n, MAX); // 불리언 배열
int q = 1;
while(q--){
int L = 0, R = 3;
int cnt = 0; // 소수 개수
for(int i = L; i <= R; i++){
if(isprime[i])
cnt++;
}
cout << cnt << "\n";
}
return 0;
}
실행 결과
2
코드 설명
이 방법은 앞서 살펴본 브루트 포스보다 훨씬 빠릅니다. 소수 여부를 미리 계산(전처리)해 두었기 때문에, 각 쿼리를 처리할 때는 단순히 범위를 한 번 순회하면 됩니다. 그 결과 전체 시간 복잡도가 O(Q*N)으로 줄어들어 이전 방식보다 상당히 개선됩니다.
여기에 에라토스테네스의 체는 소수 판별 자체를 가속화합니다. 이 알고리즘은 각 수의 소인수를 이용해 그 배수들을 일괄적으로 걸러내는 방식으로 동작하며, O(N*log(log(N)))의 시간 복잡도만에 1부터 N까지 모든 수의 소수 여부를 표시할 수 있습니다.
추가 최적화 아이디어
쿼리 개수가 매우 많다면, 소수 여부 배열을 바탕으로 누적 합(prefix sum) 배열을 미리 만들어 두면 각 쿼리를 O(1)에 처리할 수 있습니다. 이 경우 전체 복잡도는 전처리 O(N*log(log(N))) + 쿼리당 O(1)이 되어 더욱 효율적입니다.
마무리
이번 글에서는 에라토스테네스의 체를 활용해 부분 배열 내 소수의 개수를 O(Q*N) 시간 복잡도로 구하는 문제를 해결했습니다. 단순한 브루트 포스부터 최적화된 방법까지 전체 과정을 C++ 코드와 함께 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있으니, 직접 작성해 보면서 알고리즘의 동작 원리를 익혀 보시기 바랍니다.