BOJ)1747 소수&팰린드롬

문제:icpc.me/1747

N보다 큰 수 중에서 소수이면서 팰린드롬인 가장 작은 수를 구하는 문제이다.

에라토스테네스의 체를 이용하여 소수들을 구해놓은 뒤 N보다 큰 수 중에서 팰린드롬인지 검사해주면 된다.

#include <cstdio>
#include <algorithm>
using namespace std;
bool p[2000001];
int n;
bool ck(int *a, int lo, int hi) {
    if (lo >= hi)return 1;
    if (a[lo] != a[hi])return 0;
    return ck(a, lo + 1, hi - 1);
}
bool chk(int x) {
    int c = -1;
    int a[8];
    while (x) {
        a[++c] = x % 10;
        x /= 10;
    }
    return ck(a, 0, c);
}
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= 2000000; i++) {
        if (p[i])continue;
        for (int j = i + i; j <= 2000000; j += i)
            p[j] = true;
    }
    for (int i = n; i <= 2000000; i++) {
        if (p[i])continue;
        if (chk(i)) {
            printf("%d\n", i);
            return 0;
        }
    }
    return 0;
}