이 문제에서는 정수 N이 주어졌을 때, N보다 작거나 같은 모든 프로트 소수(Proth Prime)를 찾아 출력하는 것이 목표입니다.
프로트 소수란 무엇일까요?
프로트 수(Proth Number)는 다음과 같은 형태로 표현할 수 있는 양의 정수를 말합니다.
N = k × 2m + 1
여기서 k는 홀수인 양의 정수, m은 양의 정수이며, 두 값은 2m > k라는 조건을 반드시 만족해야 합니다. 이러한 프로트 수 가운데 소수에 해당하는 수를 프로트 소수(Proth Prime)라고 부릅니다.
예시: 3, 5, 13, 17 …
개념을 더 쉽게 이해하기 위해 예제를 살펴보겠습니다.
입력: N = 23 출력: 3, 5, 13, 17
문제 해결 접근 방법
이 문제는 다음 세 단계로 해결할 수 있습니다.
첫째, N 이하의 모든 소수를 구합니다. 이때 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하면 효율적으로 소수를 걸러낼 수 있습니다. 둘째, 구한 소수 각각이 프로트 수의 조건을 만족하는지 확인합니다. 셋째, 조건을 통과한 수, 즉 프로트 소수만 화면에 출력합니다.
특정 수 p가 프로트 소수인지 판별하려면 두 가지만 확인하면 됩니다. 하나는 p가 소수인지 여부이고, 다른 하나는 p − 1을 “홀수 k × 2의 거듭제곱” 꼴로 나타낼 수 있는지입니다. 아래 코드에서는 비트 연산을 이용해 어떤 수가 2의 거듭제곱인지 빠르게 검사합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int prime[1000];
void SieveOfEratosthenes(int n){
for (int i = 1; i <= n + 1; i++)
prime[i] = true;
prime[1] = false;
for (int p = 2; p * p <= n; p++) {
if (prime[p] == true) {
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
}
bool isTwosExponent(int n){
return (n && !(n & (n - 1)));
}
bool isaProthNumber(int n){
int k = 1;
while (k < (n / k)) {
if (n % k == 0) {
if (isTwosExponent(n / k))
return true;
}
k = k + 2;
}
return false;
}
bool isaProthPrime(int n){
if (isaProthNumber(n - 1)) {
if(prime[n])
return true;
else
return false;
}
else
return false;
}
int main(){
int n = 23;
cout<<"Proth Prime Numbers less than or equal to "<<n<<" are :\n";
SieveOfEratosthenes(n);
for (int i = 1; i <= n; i++)
if (isaProthPrime(i))
cout<<i<<"\t";
return 0;
}
코드 설명
SieveOfEratosthenes(): 에라토스테네스의 체를 이용해 1부터 n까지 각 수가 소수인지 여부를 배열에 저장합니다.isTwosExponent(): n이 2의 거듭제곱인지 확인합니다. n이 0이 아니면서 n과 n − 1을 비트 AND 연산한 결과가 0이라면 2의 거듭제곱입니다.isaProthNumber(): 홀수 k를 1부터 증가시키며 n을 k로 나눈 몫이 2의 거듭제곱인지 검사합니다. 몫이 2의 거듭제곱이라면 n = k × 2m 형태로 표현할 수 있다는 의미입니다.isaProthPrime(): n − 1이 프로트 수 형태를 만족하면서 n 자체가 소수일 때 참(true)을 반환합니다.
실행 결과
23 이하의 프로트 소수는 다음과 같습니다.
3 5 13 17