백준 34558 (C++) Prime Median

최초 업로드: 2025-10-19 08:53:40

최근 수정 시간: 2025-10-19 08:53:40

게시자: rlatjwls3333

카테고리: 백준

# [Gold V] Prime Median

[문제 링크](https://www.acmicpc.net/problem/34558)

## 문제 설명

$N$개의 닫힌구간 $[a_1,b_1],[a_2,b_2],\dots,[a_N,b_N]$이 주어집니다. 각 닫힌구간에서 존재하는 소수 중 중앙값을 출력하는 프로그램을 작성해 주세요.

만약, 닫힌구간 $[a_i,b_i]$에 소수가 존재하지 않거나 소수의 개수가 짝수인 경우 <code>-1</code>을 출력합니다.

## 입력

첫 줄에는 정수 $N$가 주어집니다. ($1 \leq N \leq 100\,000$)

이후 $N$개의 줄에는 $a_i, b_i$가 주어집니다. ($2 \leq a_i \leq b_i \leq 10^{6}, a_i, b_i$는 모두 정수입니다.)

## 출력

$i$번 줄에 $i$번째 구간에 대한 답을 출력합니다. 만약, $i$번째 구간 내에 소수가 존재하지 않거나 소수의 개수가 짝수일 경우, <code>-1</code>을 출력합니다.

## 풀이
100만까지의 소수를 에라토스테네스의 체로 미리 구한 후, 소수만 모아놓은 배열에서 lower_bound(a), upper_bound(b)로 범위를 구했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 1'000'001;

bool notPrime[MAX];
vector<int> primes;

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 for(int i=2;i*i<MAX;i++) {
 if(!notPrime[i]) {
 for(int j=i*i;j<MAX;j+=i) {
 notPrime[j]=true;
 }
 }
 }
 for(int i=2;i<MAX;i++) {
 if(!notPrime[i]) {
 primes.push_back(i);
 }
 }

int n; cin >> n;
 while(n--) {
 int a, b; cin >> a >> b;
 int lo = lower_bound(primes.begin(), primes.end(), a) - primes.begin();
 int hi = prev(upper_bound(primes.begin(), primes.end(), b), 1) - primes.begin();
 if((hi+lo+1)%2==0) cout << "-1\n";
 else cout << primes[(hi+lo)/2] << '\n';
 }
}
```