<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>

class Solution {
public:
    vector<int> primes;
    vector<bool> sp;

    void calcPrimes(){
        sp = vector<bool> (100001, true);
        sp[1] = false;
        for(long long i=2; i<100001; i++){
            if(sp[i]){
                primes.push_back(i);
                for(long long j=i*i; j<100001; j+=i){
                    sp[j] = false;
                }
            }
        }
    }

    bool isPrime(long long x){
        if(x<100001) return sp[x];
        for(auto el: primes) if(x%el==0) return false;
        return true;
    }

    int primePalindrome(int n) {
        calcPrimes();
        vector<int> pals;

        for(int i=1; i<=9; i++) if(isPrime(i)) pals.push_back(i);
        for(int i=1; i<999; i++){
            string sb = to_string(i);
            string se = sb;
            reverse(se.begin(), se.end());
            long long val = stoll(sb+se);
            if(isPrime(val)) pals.push_back(val);
            if(i<1000){
                for(char i='0'; i<='9'; i++){
                    val = stoll(sb+i+se);
                    if(isPrime(val)) pals.push_back(val);
                }
            }
        }

        pals.push_back(100030001);

        sort(pals.begin(), pals.end());

        int ans = *lower_bound(pals.begin(), pals.end(), n);
        return ans;
    }
};
21300