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

#include <cmath>
#include <string>
using namespace std;

class Solution {
public:
    // Helper function to check if a number is prime
    bool isPrime(int num) {
        if (num <= 1) return false;
        if (num <= 3) return true;
        if (num % 2 == 0 || num % 3 == 0) return false;
        for (int i = 5; i * i <= num; i += 6) {
            if (num % i == 0 || num % (i + 2) == 0) return false;
        }
        return true;
    }

    // Helper function to check if a number is a palindrome
    bool isPalindrome(int num) {
        string s = to_string(num);
        int left = 0, right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }

    // Function to find the smallest prime palindrome greater than or equal to n
    int primePalindrome(int n) {
        if (n <= 2) return 2;
        if (n <= 3) return 3;
        
        // We only need to check palindromes greater than or equal to n
        for (int len = 1; ; ++len) {
            // Generate palindromes of odd length
            for (int i = pow(10, len - 1); i < pow(10, len); ++i) {
                string s = to_string(i);
                string rev = s;
                reverse(rev.begin(), rev.end());
                string palinStr = s + rev.substr(1); // Odd length palindromes
                int palinNum = stoi(palinStr);
                if (palinNum >= n && isPrime(palinNum)) {
                    return palinNum;
                }
            }

            // Generate palindromes of even length
            for (int i = pow(10, len - 1); i < pow(10, len); ++i) {
                string s = to_string(i);
                string rev = s;
                reverse(rev.begin(), rev.end());
                string palinStr = s + rev; // Even length palindromes
                int palinNum = stoi(palinStr);
                if (palinNum >= n && isPrime(palinNum)) {
                    return palinNum;
                }
            }
        }
    }
};

11100