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



class Solution {
public:
	//	palindrome number with even digits is always divisible by 11
    int primePalindrome(int n) {
		if (n <= 2)
			return 2;
		if (n <= 3)
			return 3;
		if (n <= 5)
			return 5;
		if (n <= 7)
			return 7;
		if (n <= 11)
			return 11;

		for (int i = 10; i < 100000; ++i) {
			int palindrome = getPalindrome(i);

			printf("%d\n", palindrome);

			if (!isPrime(palindrome))
				continue;
			if (palindrome >= n)
				return palindrome;
		}

		return 0;
    }

private:
	inline int getPalindrome(int n) {
		int digits = 0;
		int origin = n;
		int reverse = 0;

		//	remove first digit
		n /= 10;

		while (n) {
			reverse = reverse * 10 + n % 10;
			n /= 10;
			++digits;
		}

		for (int i = 0; i < digits; ++i)
			origin *= 10;

		return origin + reverse;
	}

	inline bool isPrime(int n) {
		if (n % 2 == 0)
			return false;

		for (int i = 3; i * i <= n; i += 2)
			if (n % i == 0)
				return false;

		return true;
	}
};
7600