[1747] 소수&팰린드롬 (C++)

#include <iostream>
#include <vector>
#include <string>

using namespace std;
const int MAX = 2000000;
bool isPrime[MAX];
bool is_Palindrome(int x);

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long N;
    cin >> N;

    fill(begin(isPrime), end(isPrime), true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i < MAX; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < MAX; j += i) {
                isPrime[j] = false;
            }
        }
    }

    for (int i = N; i < MAX; i++) {
        if (isPrime[i] && is_Palindrome(i)) {
            cout << i;
            break;
        }
    }

    return 0;
}

bool is_Palindrome(int x) {
    string str = to_string(x);
    int s = 0;
    int e = str.size() - 1;
    while (s < e) {
        if (str[s] != str[e])
            return false;
        s++;
        e--;
    }

    return true;
}

 

1. 어떤 수 N의 범위가 1 <= N <= 1,000,000

=> N보다 큰 소수의 범위를 MAX(2,000,000)으로 잡는다

2. 먼저 MAX 이내의 소수를 Prime에 모두 저장한다

3. 팰린드롬 여부를 판별하는 함수를 만든다

4. MAX 이내의 수 중 소수이면서 팰린드롬인 수를 찾는다