# 0866. Prime Palindrome
###### tags: `Leetcode` `Medium`
Link: https://leetcode.com/problems/prime-palindrome/
## 思路
Write some example, you find all even length palindromes are divisible by 11.
So we need to search only palindrome with odd length.

**Time Complexity**
$O(10000$) to check all numbers 1-10000.
isPrime function is $O(sqrt(x))$ in worst case.
But only sqrt(N) worst cases for $1 \leq x \leq N$
In general it's $O(logx)$
## Code

class Solution {
    public int primePalindrome(int n) {
        if(8<=n && n<=11) return 11;
        for(int i = 1;i < 100000;i++){
            String s = Integer.toString(i), t = new StringBuilder(s).reverse().toString();
            int y = Integer.parseInt(s+t.substring(1));
            if(y>=n && isPrime(y)) return y;
        }
        return -1;
    }
    public boolean isPrime(int num){
        if(num==1) return false;
        if(num!=2&&num%2==0) return false;
        for(int i = 3;i*i <= num;i++){
            if(num%i==0) return false;
        }
        return true;
    }
}