슈퍼 프라임(Super Prime)이란?
슈퍼 프라임(super-prime, 초소수)은 전체 소수 나열에서 ‘소수 번째’ 자리에 위치한 소수를 의미합니다. 흔히 고위 소수(high-order primes)라고도 불리며, 대표적인 예로는 3, 5, 11, 17 등이 있습니다.
예제: 13 이하의 슈퍼 프라임 구하기
입력
13
출력
3, 5, 11
설명 — 먼저 13 이하의 모든 소수를 구하면 다음과 같습니다.
2, 3, 5, 7, 11, 13
이 나열에서 각 소수의 위치를 살펴보면, 2번째 소수는 3, 3번째 소수는 5, 5번째 소수는 11입니다. 위치 값 자체가 소수(2, 3, 5)이므로 3, 5, 11이 바로 슈퍼 프라임이 됩니다.
슈퍼 프라임을 찾는 알고리즘
주어진 수 n 미만의 슈퍼 프라임을 모두 찾으려면 다음 순서로 진행합니다.
1. 에라토스테네스의 체를 이용해 n 이하의 모든 소수를 구합니다.
2. 구한 소수들을 배열에 순서대로 저장합니다.
3. 배열에서 자신의 위치(순번)가 소수인 원소만 골라 출력합니다.
즉, 2번째, 3번째, 5번째, 7번째, 11번째, 13번째… 소수들만 선택하는 방식입니다.
C++ 구현 예제
#include<iostream>
using namespace std;
// 에라토스테네스의 체로 소수 판별
void SieveOfEratosthenes(int n, bool isPrime[]) {
isPrime[0] = isPrime[1] = false;
for (int i = 2; i <= n; i++)
isPrime[i] = true;
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
for (int i = p * 2; i <= n; i += p)
isPrime[i] = false;
}
}
}
// 슈퍼 프라임 출력
void superPrimes(int n) {
bool isPrime[n + 1];
SieveOfEratosthenes(n, isPrime);
int primes[n + 1], j = 0;
for (int p = 2; p <= n; p++)
if (isPrime[p])
primes[j++] = p;
// 위치(k+1번째)가 소수인 경우만 출력
for (int k = 0; k < j; k++)
if (isPrime[k + 1])
cout << primes[k] << " ";
}
int main() {
int n = 343;
cout << "Super-Primes less than " << n << " are :" << endl;
superPrimes(n);
return 0;
}실행 결과
Super-Primes less than 343 are : 3 5 11 17 31 41 59 67 83 109 127 157 179 191 211 241 277 283 331
이 코드는 시간 복잡도 O(n log log n)의 에라토스테네스의 체를 사용해 효율적으로 소수를 걸러낸 뒤, 한 번의 순회만으로 슈퍼 프라임을 추출합니다. n의 범위가 커져도 안정적으로 동작하는 것이 특징입니다.