이 문제에서는 하나의 숫자 N이 주어지며, 우리의 목표는 N보다 작은 모든 소수 삼중항(prime triplet)을 찾아 출력하는 것입니다.
소수 삼중항이란?
소수 삼중항은 세 개의 소수로 이루어진 집합으로, 다음 두 가지 형태 중 하나를 만족해야 합니다.
- (p, p+2, p+6)
- (p, p+4, p+6)
모든 소수는 위와 같은 삼중항 형태로 그룹화할 수 있는데, 그 이유는 연속된 소수 패턴에서 세 번째마다 나오는 수가 항상 6의 배수이기 때문입니다. 즉, 3개의 연속한 홀수 중 하나는 반드시 3의 배수가 되어 소수일 수 없으므로, 소수 셋이 함께 존재하려면 위의 두 형태만 가능합니다.
문제 이해를 위한 예시
입력: N = 13 출력: 5 7 11
문제 해결 접근 방법
이 문제를 해결하려면 다음 단계를 따릅니다.
- N 이하의 모든 소수를 찾습니다. 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하면 효율적으로 소수를 구할 수 있습니다.
- 각 소수 p에 대해 (p, p+2, p+6) 또는 (p, p+4, p+6) 형태의 숫자들이 모두 소수인지 확인합니다.
- 조건을 만족하는 삼중항을 모두 출력합니다.
C++ 구현 코드
다음은 위 접근 방법을 구현한 C++ 코드입니다.
#include <bits/stdc++.h>
using namespace std;
// 에라토스테네스의 체로 소수 여부 계산
void findPrimes(int n, bool prime[]) {
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
}
// 소수 삼중항을 찾아 출력하는 함수
void printPrimeTriplets(int n) {
bool prime[n + 1];
memset(prime, true, sizeof(prime));
findPrimes(n, prime);
for (int i = 2; i <= n-6; ++i) {
if (prime[i] && prime[i + 2] && prime[i + 6])
cout << i << "\t" << (i+2) << "\t" << (i+6) << endl;
else if (prime[i] && prime[i + 4] && prime[i + 6])
cout << i << "\t" << (i + 4) << "\t" << (i + 6) << endl;
}
}
int main() {
int N = 15;
cout << "Prime Triplets Less than " << N << " are :\n";
printPrimeTriplets(N);
return 0;
}실행 결과
Prime Triplets Less than 15 are : 5 7 11 7 11 13
코드 설명 및 시간 복잡도
findPrimes 함수는 에라토스테네스의 체를 구현한 것으로, 2부터 √N까지의 수에 대해 해당 수의 배수들을 모두 제거하여 소수만 남깁니다. 시간 복잡도는 O(N log log N)입니다.
printPrimeTriplets 함수는 2부터 N-6까지의 각 숫자 i에 대해 (i, i+2, i+6)과 (i, i+4, i+6) 조합이 모두 소수인지 검사하고, 조건을 만족하면 화면에 출력합니다. 이 과정의 시간 복잡도는 O(N)입니다.
따라서 전체 알고리즘의 시간 복잡도는 O(N log log N)이며, 공간 복잡도는 소수 여부를 저장하는 배열 때문에 O(N)입니다. N이 큰 경우에도 효율적으로 동작하는 최적화된 방법입니다.