Prime numbers (Hard)
IntuitionThe problem requires finding the smallest prime palindrome greater than or equal to n. A number is a palindrome if it reads the same forward and backwa
**Intuition**

The problem requires finding the smallest prime palindrome greater than or equal to n. A number is a palindrome if it reads the same forward and backward, and it is prime if it is only divisible by 1 and itself.

A brute force approach could involve checking each number sequentially, but this is inefficient. Instead, we optimize by skipping certain numbers, such as even-length palindromes (except 11), since all even-length palindromes are divisible by 11 and therefore not prime.

**Approach**

Increment n Until a Prime Palindrome Is Found

Start with n and check if it's both prime and palindromic.
If not, increment n and repeat.
Check If a Number Is a Palindrome

Convert n into a reversed version and compare it to the original.
Check If a Number Is Prime

If n < 2, it's not prime.
If n is even and not 2, it's not prime.
Check divisibility from 3 to √n to confirm primality.
Optimization: Skip Large Even-Length Palindromes

If n falls in the range (10^7, 10^8), jump directly to 10^8, as all even-length palindromes in this range are divisible by 11.
Complexity

**Time Complexity:**

Checking for a palindrome: O(d) where d is the number of digits.
Checking for primality: O(√n) in the worst case.
Since we iterate over potential candidates, the complexity is approximately O(n√n) in the worst case.
However, optimizations (like skipping even-length palindromes) reduce unnecessary iterations.

**Space Complexity:**

O(1), as we only use a few integer variables.

# Code
```java []
class Solution {
    
    public int primePalindrome(int n) {
        while (true) {
            if (isPalindrome(n) && isPrime(n)) {
                return n;
            }
            n++;
            // Optimization: Skip even-length palindromes greater than 11
            if (10_000_000 < n && n < 100_000_000) {
                n = 100_000_000;
            }
        }
    }
    
    private boolean isPalindrome(int num) {
        int original = num, reversed = 0;
        while (num > 0) {
            reversed = reversed * 10 + num % 10;
            num /= 10;
        }
        return original == reversed;
    }
    
    private boolean isPrime(int num) {
        if (num < 2) return false;
        if (num % 2 == 0 && num != 2) return false;
        for (int i = 3; i * i <= num; i += 2) {
            if (num % i == 0) return false;
        }
        return true;
    }
}

```
['Java']