C++에서 다음 회문 소수(팰린드롬 프라임) 찾기

문제 개요

이 문제에서는 하나의 정수 N이 주어지며, N보다 큰 수들 중에서 소수이면서 동시에 회문(palindrome)인 가장 작은 수, 즉 '다음 회문 소수'를 찾는 것이 목표입니다.

문제 설명: N보다 큰 수 중에서, 소수이면서 회문이기도 한 가장 작은 수를 구합니다.

회문 수(Palindrome Number): 앞에서 읽으나 뒤에서 읽으나 같은 수를 의미합니다. 예: 121, 1331, 727
소수(Prime Number): 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다.

입력·출력 예시

입력

N = 12

출력

설명

12보다 큰 회문 수를 차례대로 나열하면 22, 33, 44, 55, 66, 77, 88, 99, 101, 111, 121, … 입니다. 이 가운데 소수인 최솟값은 바로 101입니다. 참고로 22부터 99까지의 두 자릿수 회문은 모두 11의 배수이기 때문에 소수가 될 수 없습니다.

풀이 접근 방법

방법 1. 완전 탐색

N보다 큰 모든 회문 수를 하나씩 생성하고, 각각이 소수인지 검사하는 단순한 방법입니다. 구현이 쉽다는 장점이 있지만, 탐색 범위가 커지면 비효율적입니다.

방법 2. 짝수 자릿수 회문 건너뛰기 (효율적)

더 효율적인 풀이의 핵심은 다음 정리 하나로 요약됩니다.

"자릿수가 짝수인 모든 회문은 11의 배수이다."

11의 배수 판정법에 따르면, 각 자릿값을 교대로 더하고 뺀 결과가 0이면 그 수는 11의 배수입니다. 짝수 자릿수 회문은 좌우 대칭 구조이기 때문에 이 교대 합이 항상 0이 됩니다.

xyzzyx → (+x) − y + z − z + y − x = 0   ⟹   xyzzyx % 11 == 0

따라서 짝수 자릿수 회문은 11 자체를 제외하고는 절대 소수가 될 수 없습니다. 이 성질을 활용하면 짝수 자릿수 후보를 아예 건너뛰고 홀수 자릿수 회문만 검사하면 되므로, 확인해야 할 수의 개수가 크게 줄어듭니다.

C++ 구현 코드

아래 코드는 루트(root) 값 x를 키워 가며 "x + x를 뒤집은 문자열(첫 글자 제외)" 형태로 홀수 자릿수 회문을 생성하고, N 이상이면서 소수인 첫 번째 값을 반환합니다.

#include <iostream>
#include <string>
using namespace std;

// 소수 판별 함수
bool isPrime(int num) {
    if (num < 2 || num % 2 == 0)
        return num == 2;
    for (int i = 3; i * i <= num; i += 2)
        if (num % i == 0)
            return false;
    return true;
}

// N 이상인 가장 작은 회문 소수 반환
int primePalindrome(int N) {
    // 짝수 자릿수 회문 중 유일한 소수인 11 특별 처리
    if (8 <= N && N <= 11)
        return 11;
    for (int x = 1; x < 100000; ++x) {
        string s = to_string(x), r(s.rbegin(), s.rend());
        int y = stoi(s + r.substr(1)); // 홀수 자릿수 회문 생성
        if (y >= N && isPrime(y))
            return y;
    }
    return -1;
}

int main() {
    int N = 432;
    cout << "다음 회문 소수는 " << primePalindrome(N);
    return 0;
}

실행 결과

다음 회문 소수는 727

코드 동작 원리

isPrime(): 2와 홀수 약수만 확인하는 기본적인 소수 판별 함수입니다. √num까지만 검사하여 효율을 높였습니다.
primePalindrome(): N이 8~11 사이라면 답은 곧바로 11입니다. 11은 짝수 자릿수 회문 중에서 유일하게 소수인 수이기 때문입니다.
루트 x를 1부터 증가시키면서 s + reverse(s)[1:] 형태로 회문을 만듭니다. 예를 들어 x = 123이면 "123" + "21" = 12321이 됩니다.
생성된 회문이 N 이상이고 소수라면 즉시 반환합니다.

N = 432인 경우, 434부터 717 사이의 세 자릿수 회문들은 모두 2, 3, 5, 7, 11 등의 배수여서 소수가 아니며, 처음으로 소수가 되는 회문은 727입니다.

마무리

이 문제의 핵심은 모든 수를 무작정 검사하는 것이 아니라, "짝수 자릿수 회문은 11의 배수"라는 수학적 성질을 이용해 탐색 공간을 줄이는 것입니다. 이러한 최적화를 적용하면 큰 입력 값에 대해서도 다음 회문 소수를 빠르게 찾을 수 있습니다.

C++에서 다음 회문 소수(팰린드롬 프라임) 찾기 — 효율적인 풀이법