이 문제에서는 두 값 L과 R로 이루어진 Q개의 쿼리가 주어집니다. 우리의 목표는 C++를 사용하여 주어진 범위 내에 존재하는 소수들 사이의 최대 차이를 구하는 프로그램을 작성하는 것입니다.
문제 설명
각 쿼리에는 두 개의 값 L과 R이 주어집니다. 우리는 주어진 범위 [L, R] 안에서 가장 큰 소수와 가장 작은 소수의 차이, 즉 최대 차이를 찾아야 합니다. 만약 범위 내에 소수가 하나도 존재하지 않는다면 0을 출력합니다.
예제로 문제 이해하기
입력
Q = 2 2 45 14 16
출력
41 0
설명
쿼리 1: 범위 [2, 45] 내에서 가장 작은 소수는 2이고, 가장 큰 소수는 43입니다. 따라서 최대 차이는 43 - 2 = 41입니다.
쿼리 2: 범위 [14, 16] 내에는 소수가 존재하지 않으므로 출력은 0입니다.
해결 접근 방법
이 문제를 효율적으로 해결하기 위해 다음과 같은 단계를 따릅니다.
- 소수 전처리: 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 0부터 100004까지의 모든 수에 대해 소수 여부를 미리 계산해 둡니다.
- 범위 탐색: 각 쿼리가 주어지면 L부터 R 방향으로 순회하며 처음 만나는 소수(범위 내 가장 작은 소수)를 찾고, 반대로 R부터 L 방향으로 순회하며 처음 만나는 소수(범위 내 가장 큰 소수)를 찾습니다.
- 차이 계산: 두 소수의 차이를 반환합니다. 범위 내에 소수가 없으면 초기값 0이 그대로 반환됩니다.
전처리에 필요한 시간 복잡도는 O(N log log N)이며, 각 쿼리는 최악의 경우 O(R - L + 1)의 시간에 처리됩니다.
솔루션 구현 예제
#include <bits/stdc++.h>
using namespace std;
bool primeNumber[100005];
// 에라토스테네스의 체로 소수 여부를 미리 계산
void findPrimes(){
memset(primeNumber, true, sizeof(primeNumber));
for (int i = 2; i * i < 100005; i++) {
if (primeNumber[i]) {
for (int j = i + i; j < 100005; j += i)
primeNumber[j] = false;
}
}
}
// 범위 [L, R] 내 소수의 최대 차이를 반환
int findPrimeInRange(int L, int R) {
int LPrime = 0;
int RPrime = 0;
// L부터 오름차순으로 탐색하여 가장 작은 소수 찾기
for(int i = L; i <= R; i++){
if(primeNumber[i] == true){
LPrime = i;
break;
}
}
// R부터 내림차순으로 탐색하여 가장 큰 소수 찾기
for(int j = R; j >= L; j--){
if(primeNumber[j] == true){
RPrime = j;
break;
}
}
return (RPrime - LPrime);
}
int main() {
int Q = 3;
int query[Q][2] = {{4, 15}, {32, 37}, {54, 1100}};
findPrimes();
for (int i = 0; i < Q; i++)
cout<<"쿼리 "<<(i+1)<<": 소수 간의 최대 차이는 "<<findPrimeInRange(query[i][0], query[i][1])<<"\n";
return 0;
}
출력 결과
쿼리 1: 소수 간의 최대 차이는 8 쿼리 2: 소수 간의 최대 차이는 0 쿼리 3: 소수 간의 최대 차이는 1038
마무리
이처럼 에라토스테네스의 체를 활용해 소수 정보를 미리 구해두면, 여러 개의 쿼리를 빠르게 처리할 수 있습니다. 특히 쿼리의 개수가 많고 범위가 넓은 상황에서 전처리 기반 접근 방식이 얼마나 효율적인지 확인할 수 있는 대표적인 예제입니다.