<p>Given an integer n, return <em>the smallest <strong>prime palindrome</strong> greater than or equal to </em><code>n</code>.</p>

<p>An integer is <strong>prime</strong> if it has exactly two divisors: <code>1</code> and itself. Note that <code>1</code> is not a prime number.</p>

<ul>
	<li>For example, <code>2</code>, <code>3</code>, <code>5</code>, <code>7</code>, <code>11</code>, and <code>13</code> are all primes.</li>
</ul>

<p>An integer is a <strong>palindrome</strong> if it reads the same from left to right as it does from right to left.</p>

<ul>
	<li>For example, <code>101</code> and <code>12321</code> are palindromes.</li>
</ul>

<p>The test cases are generated so that the answer always exists and is in the range <code>[2, 2 * 10<sup>8</sup>]</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> n = 6
<strong>Output:</strong> 7
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> n = 8
<strong>Output:</strong> 11
</pre><p><strong class="example">Example 3:</strong></p>
<pre><strong>Input:</strong> n = 13
<strong>Output:</strong> 101
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>8</sup></code></li>
</ul>

vector<bool> isprime;
vector<int> primeList;
const int n = 1e7;

// ((n/2) + (n/3) + (n/5) + ....)
// n((1/2) + (1/3) + (1/5) + ....)
// H(n) = ((1/1) + (1/2) + (1/3) + (1/4) + (1/5) + ....) = O(logn)
// ((1/2) + (1/3) + (1/5) + ....) = O(loglogn)

//O(nloglogn)
auto eratosthenes = [] () {
    isprime.assign(n + 5, true);
    isprime[0] = false;
    isprime[1] = false;

    int sqrtSize = sqrt(n + 5);

    for (int i = 2 ; i <= sqrtSize ; ++i ) {
        if (isprime[i] == true) {
            //start from i^2 -> i * (i + 1) -> i * (i + 2) -> .....
            for (int j = i * i ; j <= n ; j += i ) {
                isprime[j] = false;
            }
        }
    }

    for (int i = 2 ; i <= isprime.size() ; ++i ) {
        if (isprime[i] == true) {
            primeList.push_back(i);
        }
    }

    return 0;
}();

class Solution {
public:
    int primePalindrome(int n) {
        if (9989900 <= n && n <= 1e8)
            return 100030001;

        auto it = ranges::lower_bound(primeList, n);

        auto isPalindrome = [] (string str) {
            int left = 0, right = str.size() - 1;
            while (left < right) {
                if (str[left++] != str[right--]) {
                    return false;
                }
            }
            return true;
        };

        while (it != primeList.end()) {
            if (isPalindrome(to_string(*it))) {
                return *it;
            }
            it = next(it);
        }

        return -1; // never come here
    }
};
19200