[백준 1747] 소수&팰림드롬 [C]

백준 - 1747

---

풀이

에라토스테네스의 체로 소수가 아닌 수들을 찾고, 입력받은 N부터 소수인 수들중에 팰림드롬인지 확인해서 맞으면 해당 수를 출력하고 탐색을 종료하면 된다.

 

단, 98689 이후의 수들이 갖는 최소의 펠림드롬 소수는 1003001이므로 예외처리를 해주어야 한다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>
#define MAX 1000001
bool cNum[MAX] = {0, 1};
int main(){
    int sq = sqrt(MAX);
    for (int i = 2; i <= sq; i++)
        if(!cNum[i])
            for (int j = 2*i; j < MAX; j += i)
                cNum[j] = true;	
						
    int N;
    scanf("%d", &N);
    if (N > 98689) puts("1003001");
    else 
        for (int i = N; i < MAX; i++)
            if (!cNum[i]){
                char str[7];
                sprintf(str, "%d", i);
                int len = strlen(str), j;
                for (j = 0; j < len/2; j++)
                    if (str[j] != str[len-j-1]) break;
	
                if (j == len/2){
                    printf("%d", i);
                    break;
                }
            }	
}

---

출처

1747번: 소수&팰린드롬