LeetCode 866. Prime Palindrome

原题链接在这里：https://leetcode.com/problems/prime-palindrome/

题目：

Find the smallest prime palindrome greater than or equal to N.

Recall that a number is prime if it's only divisors are 1 and itself, and it is greater than 1. 

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

Recall that a number is a palindrome if it reads the same from left to right as it does from right to left. 

For example, 12321 is a palindrome.

Example 1:

Input: 6
Output: 7

Example 2:

Input: 8
Output: 11

Example 3:

Input: 13
Output: 101

Note:

• 1 <= N <= 10^8
• The answer is guaranteed to exist and be less than 2 * 10^8.

题解：

For palindrome, only odd number length could be prime.

Because all even length could be divided by 11. like 1111 % 11 = 0.

Check all odd length palindrome, if it is prime, return it.

AC Java:

class Solution {
    public int primePalindrome(int N) {
        if(N >= 8 && N <= 11){
            return 11;
        }
        
        for(int i = 1; i <= 100000; i++){
            String half = "" + i;
            String can = half + new StringBuilder(half.substring(0, half.length() - 1)).reverse().toString();
            
            int canVal = Integer.valueOf(can);
            if(canVal >= N && isPrime(canVal)){
                return canVal;
            }
        }
        
        return -1;
    }
    
    private boolean isPrime(int n){
        if(n < 2 || n % 2 == 0){
            return n == 2;
        }
        
        for(int i = 3; i * i <= n; i += 2){
            if(n % i == 0){
                return false;
            }
        }
        
        return true;
    }
    
}