티스토리 뷰

알고리즘 관련/BOJ

BOJ)1747 소수&팰린드롬

JASON 자손9319 2017. 3. 23. 16:31

문제:icpc.me/1747


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


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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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;
}
 
cs





'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2660 회장뽑기  (0) 2017.03.23
BOJ)1755 숫자놀이  (0) 2017.03.23
BOJ)1747 소수&팰린드롬  (0) 2017.03.23
BOJ)10835 카드게임  (0) 2017.03.23
BOJ)7535 A Bug's Life  (0) 2017.03.22
BOJ)3747 완벽한 선거!  (0) 2017.03.22
댓글
댓글쓰기 폼