1
class Solution {
2
 public:
3
  bool isPrime(int N) {
4
    if (N < 2) return false;
5
    int R = (int)sqrt(N);
6
    for (int d = 2; d <= R; ++d)
7
      if (N % d == 0) return false;
8
    return true;
9
  }
10

11
 public:
12
  int reverse(int N) {
13
    int ans = 0;
14
    while (N > 0) {
15
      ans = 10 * ans + (N % 10);
16
      N /= 10;
17
    }
18
    return ans;
19
  }
20

21
 public:
22
  int primePalindrome(int n) {
23
    while (true) {
24
      if (n == reverse(n) && isPrime(n)) return n;
25
      n++;
26

27
      // Any even length palindrome must be divisble by 11
28
      // so we will skip numbers N = [10,000,000, 99,999,999]
29
      if (10000000 < n && n < 100000000) n = 100000000;
30
    }
31
  }
32
};