숫자 N이 주어졌을 때, N보다 큰 수 중에서 소수이면서 동시에 회문(palindrome)인 가장 작은 수를 찾는 것이 목표입니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 같은 수를 의미합니다. 예시를 통해 살펴보겠습니다.
입력
N = 10
출력
11
11은 소수이면서 회문이기도 하므로, 10보다 큰 첫 번째 소수 회문입니다.
알고리즘
숫자 N을 초기화합니다.
주어진 수가 소수인지 판별하는 함수를 작성합니다.
주어진 수가 회문인지 판별하는 함수를 작성합니다.
N + 1부터 시작하여 다음 소수 회문을 찾을 때까지 반복하는 루프를 작성합니다.
- 현재 수가 소수이면서 회문인지 확인합니다.
- 두 조건을 모두 만족하면 해당 수를 반환하고 종료합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include<bits/stdc++.h>
using namespace std;
// 소수 판별 함수
bool isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
// 회문 판별 함수
bool isPalindrome(int n) {
int num = n, digit, rev = 0;
while (num) {
digit = num % 10;
rev = (rev * 10) + digit;
num = num / 10;
}
return n == rev ? true : false;
}
// N보다 큰 가장 작은 소수 회문 찾기
int getNextSmallestPrimePalindrome(int n) {
int i = n + 1;
while (true) {
if (isPrime(i) && isPalindrome(i)) {
return i;
}
i += 1;
}
}
int main() {
int N = 15;
cout << getNextSmallestPrimePalindrome(N) << endl;
return 0;
}
출력
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
101
N이 15일 경우, 17은 소수이지만 회문이 아니며, 두 자리 회문(22, 33, 44 등)은 모두 11의 배수라서 소수가 될 수 없습니다. 따라서 15보다 큰 첫 번째 소수 회문은 세 자리 수인 101이 됩니다.
코드 설명
isPrime 함수
2부터 √n까지의 수로 나누어 떨어지는지 검사하여 소수 여부를 판별합니다. 약수는 대칭적으로 존재하므로 제곱근까지만 확인하면 충분하며, 시간 복잡도는 O(√n)입니다.
isPalindrome 함수
숫자의 끝자리부터 한 자리씩 추출하여 뒤집힌 수(rev)를 만든 뒤, 원래 수와 비교함으로써 회문 여부를 판별합니다.
getNextSmallestPrimePalindrome 함수
N + 1부터 시작하여 1씩 값을 증가시켜 가면서, 소수이면서 회문인 첫 번째 수를 찾아 반환합니다. 답이 항상 존재하므로 무한 루프 안에서 안전하게 탐색할 수 있습니다.
참고: 성능 최적화 팁
짝수 자릿수의 회문은 항상 11의 배수이므로 소수가 될 수 없다는 성질을 활용하면 좋습니다. N이 매우 클 경우에는 1씩 증가하며 일일이 검사하는 대신, 홀수 자릿수의 회문만 생성한 뒤 소수 여부만 확인하는 방식으로 탐색 속도를 크게 개선할 수 있습니다.