에라토스테네스의 체를 이용하여 푸는 문제이다. 먼저 에라토스테네스의 체를 이용하여 소수를 구해주었다. 그 후 반복문을 돌면서 소수인 수 중에서 팰린드롬에 해당하는지 확인을 한 후 해당하면 저장을 한 후 출력해주었다. 로직 자체는 어렵지 않은 문제였다. 범위를 처음에는 2,000,000으로 두었는데 이때 범위 문제로 계속해서 틀렸었고 범위를 1,003,002로 두니 통과하였다. 범위 문제로도 틀릴 수 있다는 것을 알아두자.
#include <iostream>
#include <string>
#define SIZE 1003002
using namespace std;
int N;
bool p[SIZE];
void prime() {
for (int i = 2; i <= SIZE; i++) {
if (p[i]) continue;
for (int j = i + i; j <= SIZE; j += i) {
p[j] = true;
}
}
}
bool check(int n) {
string s = to_string(n);
int start = 0;
int end = s.size() - 1;
while (start <= end) {
if (s[start] == s[end]) {
start++;
end--;
}
else {
return false;
}
}
return true;
}
void solution() {
int result = 0;
for (int i = N; i <= SIZE; i++) {
if (p[i]) continue;
if (check(i)) {
result = i;
break;
}
}
result = result == 1 ? 2 : result;
cout << result;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
prime();
solution();
return 0;
}