# Prime Palindrome
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/prime-palindrome)
Canonical: https://scaleengineer.com/dsa/problems/prime-palindrome
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Number Theory](https://scaleengineer.com/dsa/patterns/number-theory)
---
## Problem
Given an integer n, return _the smallest **prime palindrome** greater than or equal to_ `n`.

An integer is **prime** if it has exactly two divisors: `1` and itself. Note that `1` is not a prime number.

* For example, `2`, `3`, `5`, `7`, `11`, and `13` are all primes.

An integer is a **palindrome** if it reads the same from left to right as it does from right to left.

* For example, `101` and `12321` are palindromes.

The test cases are generated so that the answer always exists and is in the range `[2, 2 * 108]`.

**Example 1:**

**Input:** n = 6
**Output:** 7

**Example 2:**

**Input:** n = 8
**Output:** 11

**Example 3:**

**Input:** n = 13
**Output:** 101

**Constraints:**

* `1 <= n <= 108`

# Approaches
## Brute Force Iteration
This approach involves iterating through integers starting from `n`. For each integer, we perform two checks: first, whether it's a palindrome, and second, whether it's a prime number. The first integer that satisfies both conditions is the smallest prime palindrome greater than or equal to `n` and is returned.
**Time:** O(D * sqrt(M)), where M is the resulting prime palindrome and D is the difference `M - n`. In the worst case, the gap D can be very large, making this approach too slow. · **Space:** O(log M), where M is the resulting prime palindrome. This space is used to store the number as a string for the palindrome check.
**Pros:** Simple to understand and implement.
**Cons:** Highly inefficient and will likely result in a "Time Limit Exceeded" error for larger inputs.; Performs a costly primality test on many numbers that are not palindromes.
### Explanation
The algorithm begins by checking every integer `num` starting from the input `n`. For each `num`, it first verifies if it's a palindrome. This can be done by converting the number to a string and comparing it with its reverse. If the number is a palindrome, the algorithm proceeds to check if it's also a prime number. The primality test involves checking for divisibility from 2 up to the square root of the number. The loop continues, incrementing `num` by one at each step, until a number is found that is both a palindrome and a prime. This number is then the desired result.

```java
class Solution {
    public int primePalindrome(int n) {
        while (true) {
            if (isPalindrome(n) && isPrime(n)) {
                return n;
            }
            n++;
            // All 8-digit palindromes are divisible by 11.
            // If n reaches 10,000,000, we can skip to 100,000,000.
            if (n > 10_000_000 && n < 100_000_000) {
                n = 100_000_000;
            }
        }
    }

    private boolean isPalindrome(int x) {
        if (x < 0 || (x != 0 && x % 10 == 0)) return false;
        int reversed = 0;
        int original = x;
        while (x > 0) {
            reversed = reversed * 10 + x % 10;
            x /= 10;
        }
        return original == reversed;
    }

    private boolean isPrime(int x) {
        if (x < 2) return false;
        if (x % 2 == 0) return x == 2;
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Start a loop with a variable `num` initialized to `n`.
- In each iteration, check if `num` is a palindrome. A number is a palindrome if its string representation is the same as its reverse.
- If `num` is a palindrome, check if it is a prime number. A number `x` is prime if it's greater than 1 and not divisible by any integer from 2 up to its square root.
- If `num` is both a palindrome and a prime, it is our answer. Return `num`.
- If not, increment `num` and continue the loop.
- A small optimization can be added: all 8-digit palindromes are divisible by 11. So, if `num` reaches `10^7`, we can skip directly to `10^8`.

## Generate Palindromes and Test Primality
A more efficient approach is to generate only palindromic numbers and then test them for primality. This avoids checking every number between `n` and the answer. We can further optimize this by observing a mathematical property: all even-length palindromes, except for 11, are divisible by 11 and thus not prime. Therefore, we only need to generate and test odd-length palindromes.
**Time:** O(K_ans * sqrt(P_ans)), where `P_ans` is the answer and `K_ans` is its root. Since `K_ans` is approximately `sqrt(P_ans)`, the complexity is roughly `O(P_ans)`. However, in practice, we only check a small number of palindromes starting from `n`, making it very fast. · **Space:** O(log K), where K is the root of the palindrome. This space is for storing the string representation of the root.
**Pros:** Significantly more efficient as it drastically reduces the number of primality tests.; Leverages a mathematical property of palindromes to simplify the search space.
**Cons:** The logic for generating palindromes from a root is slightly more complex than a simple iteration.
### Explanation
This method focuses on the fact that palindromes are sparse. Instead of checking every number, we only generate candidates that are already palindromes. An odd-length palindrome is uniquely determined by its first half, which we call the 'root'. For example, the palindrome `12321` is formed from the root `123`. 

The algorithm iterates through roots `k` (1, 2, 3, ...), constructs the full odd-length palindrome from each root, and then checks two conditions: if the palindrome is greater than or equal to `n`, and if it's prime. Since the roots are processed in increasing order, the generated palindromes are also in increasing order. The first palindrome that satisfies both conditions is the smallest prime palindrome and is the correct answer.

```java
class Solution {
    public int primePalindrome(int n) {
        // Handle small cases and the only even-length prime palindrome
        if (n >= 8 && n <= 11) {
            return 11;
        }

        // Generate odd-length palindromes from their roots.
        // For n <= 10^8, the answer is <= 2*10^8.
        // A 9-digit palindrome has a 5-digit root.
        // A root of 20000 generates 200000002. So we can cap the root loop.
        for (int k = 1; k < 20000; k++) {
            String s = Integer.toString(k);
            String reversed_s = new StringBuilder(s).reverse().toString();
            int p = Integer.parseInt(s + reversed_s.substring(1));

            if (p >= n && isPrime(p)) {
                return p;
            }
        }
        
        // The problem guarantees an answer exists in the range [2, 2 * 10^8],
        // which is covered by the loop above. For example, the next prime
        // palindrome after 10^8 is 100300301, from root k=10030.
        return -1; // Should not be reached.
    }

    private boolean isPrime(int x) {
        if (x < 2 || x % 2 == 0) {
            return x == 2;
        }
        for (int i = 3; i * i <= x; i += 2) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Handle edge cases: If `n` is between 8 and 11, the answer is 11, the only even-length prime palindrome.
- Iterate through possible roots `k` starting from 1. For an answer up to `2*10^8`, the root will have at most 5 digits, so we can cap the loop for `k` at `20000`.
- For each root `k`, construct the corresponding odd-length palindrome `p`.
  - Convert `k` to a string `s`.
  - Create a reversed version of `s`, let's call it `rev_s`.
  - The palindrome string is `s` concatenated with `rev_s` excluding its first character (e.g., root `123` -> `s="123"`, `rev_s="321"`, palindrome is `"123" + "21"` -> `12321`).
  - Convert this string back to an integer `p`.
- Check if the generated palindrome `p` is greater than or equal to `n`.
- If it is, check if `p` is prime.
- If `p` is also prime, return `p`. Since we generate palindromes in increasing order, this will be the smallest one.

# Solutions
### Java

```java
class Solution {
public
  int primePalindrome(int n) {
    while (true) {
      if (reverse(n) == n && isPrime(n)) {
        return n;
      }
      if (n > 10000000 && n < 100000000) {
        n = 100000000;
      }
      ++n;
    }
  }
private
  boolean isPrime(int x) {
    if (x < 2) {
      return false;
    }
    for (int v = 2; v * v <= x; ++v) {
      if (x % v == 0) {
        return false;
      }
    }
    return true;
  }
private
  int reverse(int x) {
    int res = 0;
    while (x != 0) {
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int primePalindrome(int n) {
    while (1) {
      if (reverse(n) == n && isPrime(n))
        return n;
      if (n > 10000000 && n < 100000000)
        n = 100000000;
      ++n;
    }
  }
  bool isPrime(int x) {
    if (x < 2)
      return false;
    for (int v = 2; v * v <= x; ++v)
      if (x % v == 0)
        return false;
    return true;
  }
  int reverse(int x) {
    int res = 0;
    while (x) {
      res = res * 10 + x % 10;
      x /= 10;
    }
    return res;
  }
};

```

### Python

```python
class Solution:
    def primePalindrome(self, n: int) -> int: def is_prime(x): if x < 2: return False v = 2 while v * v <= x: if x % v == 0: return False v += 1 return True def reverse(x): res = 0 while x: res = res * 10 + x % 10 x //= 10 return res while 1: if reverse(n) == n and is_prime(n): return n if 10 ** 7 < n < 10 ** 8: n = 10 ** 8 n += 1

```