백준 1747번 C++ 풀이

https://www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

시간 제한	메모리 제한	solved.ac 티어
2초	256MB	실버 1

문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.

어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다.

출력

첫째 줄에 조건을 만족하는 수를 출력한다.

예제 입력1

31

예제 출력1

101

---

에라토스테네스의 체를 통해 소수를 판별하고 회문인지 판단하여 이 둘이 모두 참인 경우 출력한다.

 

#include <bits/stdc++.h>
using namespace std;
#define MAX_SIZE 2000001

bool is_palidrome(const int n){
    string rev;
    int num = n;
    while(num) {
        rev += (num % 10) + '0';
        num /= 10;
    }
    return n == stoi(rev);
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    vector<bool> seive(MAX_SIZE, true);
    // bool seive[MAX_SIZE];
    // fill(seive, seive + MAX_SIZE, true);
    seive[0] = seive[1] = false;
    
    // initializing
    for(int i = 2; i < MAX_SIZE; i++) {
        if (seive[i]) { 
            for (int p = 2; i*p < MAX_SIZE; p++) {
                seive[i*p] = false;
            }
        }
    }

    cin >> n;
    
    for(int i = n; ; i++) {
        if(seive[i] && is_palidrome(i)) {
            cout << i;
            break;
        }
    }
}