[C/C++] 백준 #1747 소수&팰린드롬(수학)

이번 문제는 n 이상의 수중에 가장 작은 소수이면서 팰린드롬이 되는 수를 찾는 문제입니다.

 

pellindrome

 

구현을 위한 핵심은 다음과 같습니다.

1) n의 앞부분 절반의 수를 구합니다.  예를 들어서 120의 경우라면 3자리 숫자에 12가 됩니다.  31과 같은 숫자는 2자리 수에 3이 됩니다.

2) 절반의 수를 이용해서 같은 자리수의 팰린드롬을 구합니다.  120의 경우에는 121이 팰린드롬 수가 됩니다.  31의 경우에는 33이 팰린드롬이 됩니다.  이 수가 n 이상의 수가 된다면, 통과이고, 그렇지 않다면 절반의 수에 1을 더합니다.  이 수는 반드시 n보다 큰 수가 되기 때문에 1을 더하는 것으로 충분합니다.

3) 그 수부터 시작해서 팰린드롬이 되는 수 중에 소수인 수를 찾습니다.  여기서 사실 알고리즘 효율을 위해서 맨 첫자리수가 홀수인 것을 찾을 수 있습니다.  저는 그렇게 구현하지 않았지만, 2 초과 수중 소수는 모두 홀수이기 때문에 n이 2 이하일 때에는 2를 출력하는 예에만 처리하면 많이 줄일 수 있습니다.  120의 경우 12로 시작하는 수이므로 131이 답이 될겁니다.  31의 경우에는 3, 5, 7, 9 모두 11의 배수가 되므로 답이 없습니다.  이 경우에는 자릿수를 하나 증가하고, 첫자리가 1로 해서 풀면 됩니다.  첫자리가 1인 3자리수는 101과 같은 수가 있기 때문에 for 루프를 이용해도 바로 답이 나옵니다.

 

프로그램 자체는 비효율적인 부분이 있습니다.  첫 자리수가 홀수가 아니라면 건너띄는 부분을 만들어야할 것으로 보입니다.  예를 들어서 200이라고 한다면, 20부터 29까지의 검사는 의미가 없습니다.  자릿수가 늘어나면, 더 문제가 될겁니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//    baekjoon #1747 - Prime Numbers and Pelindrome
//        - by Aubrey Choi
//        - created at 2019-06-13
//--------------------------------------------------------------------
#include <stdio.h>

bool isprime(int n)
{
    if(n == 2) return true;
    if(n < 2 || n % 2 == 0) return false;
    for(int s=3;s*s<=n;s+=2) if(!(n%s)) return false;
    return true;
}
int makeperidrom(int s, int t)
{
    int r = t, i;
    int x = (s%2)?t/10:t;
    for(i=0;i<s/2;i++) { r=r*10+x%10; x/=10; }
    return r;
}
int main()
{
    int n, s, t;
    scanf("%d", &n);
    for(s = 1, t = 10; t <= n; s++, t *= 10);
    t = n;
    for(int i = 0; i < s / 2; i++) t /= 10;
    if(makeperidrom(s, t) < n) t++;
    for(;;)
    {
        int u = 10;
        for(int i = 0; i < (s - 1) / 2; i++, u *= 10);
        for(int i = t; i < u; i++)
        {
            int p = makeperidrom(s, i);
            if(isprime(p)) { printf("%d\n", p); return 0; }
        }
        s++; t = 1;
        for(int i = 0; i < (s - 1) / 2; i++, t *= 10);
    }
}