균형 소수란 무엇인가?
균형 소수(Balanced Prime)는 바로 앞의 소수와 바로 뒤의 소수와의 거리(차이)가 서로 같은 소수를 의미합니다. 쉽게 말해, 인접한 이전 소수와 다음 소수의 평균값이 되는 소수입니다.
어떤 소수가 균형 소수가 되려면 다음 공식을 만족해야 합니다.
Pn = (Pn-1 + Pn+1) / 2
여기서 n은 소수 집합에서 해당 소수 Pn의 순서(인덱스)를 나타냅니다.
소수의 순서 집합은 2, 3, 5, 7, 11, 13, … 과 같이 나열됩니다.
처음 몇 개의 균형 소수는 5, 53, 157, 173, … 입니다.
예를 들어 5의 경우, 이전 소수는 3이고 다음 소수는 7입니다. (3 + 7) / 2 = 5이므로 5는 균형 소수입니다.
문제 정의
이 문제에서는 하나의 수 n이 주어지며, 우리는 n번째 균형 소수를 찾아야 합니다.
예시를 살펴보겠습니다.
입력 : n = 3
출력 : 157
즉, 세 번째 균형 소수는 157이라는 뜻입니다.
해결 접근 방법
문제를 해결하는 절차는 다음과 같습니다.
1. 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 일정 범위까지의 모든 소수를 생성합니다.
2. 생성된 소수들을 배열(또는 벡터)에 저장합니다.
3. 각 소수에 대해 인접한 이전 소수와 다음 소수의 평균이 자기 자신과 같은지 확인합니다.
4. 균형 소수를 찾을 때마다 카운트를 증가시키고, 카운트가 n과 같아지면 해당 소수를 출력합니다.
C++ 구현 예제
#include<bits/stdc++.h>
#define MAX 501
using namespace std;
int balancedprimenumber(int n){
bool prime[MAX+1];
memset(prime, true, sizeof(prime));
for (int p = 2; p*p <= MAX; p++){
if (prime[p] == true)
{
for (int i = p*2; i <= MAX; i += p)
prime[i] = false;
}
}
vector<int> v;
for (int p = 3; p <= MAX; p += 2)
if (prime[p])
v.push_back(p);
int count = 0;
for (int i = 1; i < v.size(); i++){
if (v[i] == (v[i+1] + v[i - 1])/2)
count++;
if (count == n)
return v[i];
}
}
int main(){
int n = 3;
cout<<balancedprimenumber(n)<<endl;
return 0;
}
실행 결과
157
코드 설명
위 코드의 동작 원리를 단계별로 살펴보겠습니다.
1. 소수 판별 (에라토스테네스의 체): bool 타입 배열 prime을 모두 true로 초기화한 후, 2부터 시작해 각 소수의 배수들을 false로 표시하여 합성수를 제거합니다. 이렇게 하면 MAX(501)까지의 모든 소수를 효율적으로 구할 수 있습니다.
2. 소수 목록 저장: 3부터 홀수만 검사하여 소수인 값들을 벡터 v에 순서대로 저장합니다. 짝수 중 유일한 소수인 2는 균형 소수가 될 수 없으므로 제외해도 무방합니다.
3. 균형 소수 판별: 벡터를 순회하면서 현재 소수 v[i]가 이전 소수 v[i-1]과 다음 소수 v[i+1]의 평균과 같은지 확인합니다. 조건을 만족하면 count를 1씩 증가시킵니다.
4. 결과 반환: count가 입력값 n과 같아지는 순간, 해당 소수 v[i]를 반환합니다. n = 3일 때 세 번째 균형 소수인 157이 출력됩니다.
마무리
균형 소수는 소수 사이의 간격이 대칭을 이루는 특별한 소수입니다. 에라토스테네스의 체로 소수를 미리 구해 놓으면 인접 소수와의 비교만으로 균형 소수를 빠르게 찾을 수 있습니다. 시간 복잡도는 소수 생성에 O(MAX log log MAX), 균형 소수 탐색에 O(π(MAX))로 매우 효율적입니다.