이 문제에서는 정수 N이 주어지고, N보다 작은 모든 안전 소수(safe prime)를 출력해야 합니다.
안전 소수란 무엇인가?
안전 소수(safe prime)는 (2×p)+1 형태로 나타낼 수 있는 소수를 의미하며, 이때 p 역시 소수여야 합니다. 여기서 p와 같은 소수를 소피 제르맹 소수(Sophie Germain prime)라고 부릅니다.
예시: 5 = (2×2)+1, 7 = (2×3)+1, 11 = (2×5)+1
문제를 더 잘 이해하기 위해 몇 가지 예를 살펴보겠습니다.
입력: N = 12
출력: 5 7 11
문제 해결 접근 방법
이 문제는 다음 단계로 해결할 수 있습니다.
- 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 N 이하의 모든 소수를 찾습니다.
- 각 소수 i에 대해 (2×i)+1이 N 이하이면서 소수인지 확인합니다.
- 조건을 만족하는 수가 바로 안전 소수이므로, 이를 모두 출력합니다.
이 방법의 시간 복잡도는 에라토스테네스의 체에 의해 지배되므로 O(n log log n)입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 안전 소수를 출력하는 함수
void printPrime(int n){
cout<<n<<"\t";
}
void generateSafePrimes(int n){
int prime[n + 1];
// 모든 수를 소수로 초기화
for (int i = 2; i <= n; i++)
prime[i] = 1;
prime[0] = prime[1] = 0;
// 에라토스테네스의 체로 소수 판별
for (int p = 2; p * p <= n; p++) {
if (prime[p] == 1) {
for (int i = p * 2; i <= n; i += p)
prime[i] = 0;
}
}
// (2*i)+1이 소수인지 확인하여 안전 소수 표시
for (int i = 2; i <= n; i++) {
if (prime[i] != 0) {
int temp = (2 * i) + 1;
if (temp <= n && prime[temp] != 0)
prime[temp] = 2;
}
}
// 표시된 안전 소수 출력
for (int i = 5; i <= n; i++)
if (prime[i] == 2)
printPrime(i);
}
// 메인 함수
int main(){
int n = 34;
cout<<"safe Prime numbers less than "<<n<<" are :\n";
generateSafePrimes(n);
return 0;
}
출력 결과
34보다 작은 안전 소수는 다음과 같습니다.
5 7 11 23
코드 동작 원리
위 코드는 크게 세 부분으로 구성됩니다.
- 소수 찾기: 에라토스테네스의 체를 이용해 2부터 n까지의 수 중 소수만 남깁니다.
- 안전 소수 판별: 소수 i에 대해 (2×i)+1이 범위 내의 소수라면, 해당 수를 안전 소수로 표시합니다(배열 값을 2로 변경).
- 결과 출력: 안전 소수로 표시된 값만 골라 출력합니다. 가장 작은 안전 소수는 5이므로 5부터 순회합니다.
이처럼 에라토스테네스의 체를 한 번만 수행하면 소수 판별과 안전 소수 판별을 모두 효율적으로 처리할 수 있어, 큰 N에 대해서도 빠른 실행 속도를 보장합니다.