leetcode 866. Prime Palindrome | 866. prime palindromes

subject

https://leetcode.com/problems/prime-palindrome/

Answer key

Refer to the answer ：https://leetcode.com/problems/prime-palindrome/solution/

When you do it yourself , I split the odd palindrome string from the even palindrome string , Finally, return the minimum value between the two palindromes , I think it's more rigorous , Although this rigor can be mathematically proved to be unnecessary . Because if the digits are different , The size of the result does not increase monotonically , You shouldn't just return.

for example , Because if you count odd numbers first , If you count even numbers again , Odd numbers are one bit less than even numbers , In this way, it is possible to return the minimum value of error ：

1002001	（ Suppose it is false）
10022001（ Suppose it is false）
1003001	（ Suppose it is false）
10033001（ Suppose it is true, Straight back , Is the minimum value of error ）
1004001	（ Suppose it is true, This is the real minimum ）

As for why the answer is written like this, there is no problem , Because All palindrome with even digits is multiple of 11. Equivalent to greater than 11 Even numbers of will return false, Will not cause the above example to return 10033001 The situation of .

class Solution {
    
    public int primePalindrome(int n) {
    
        if (n == 1) return 2;

        long even = primePalindromeEven(n);
        long odd = primePalindromeOdd(n);
        return (int) Math.min(even, odd);
    }

    public long primePalindromeEven(int n) {
    
        for (int L = 1; L <= 5; L++) {
     //  Palindrome root Number of digits L
            for (int root = (int) Math.pow(10, L - 1); root < Math.pow(10, L); root++) {
     //  Traversal digit is L All palindromes of root
                //  Even number palindrome string 
                StringBuilder sb = new StringBuilder(String.valueOf(root));
                for (int i = L - 1; i >= 0; i--) {
    
                    sb.append(sb.charAt(i));
                }
                long num = Long.parseLong(String.valueOf(sb));
                if (num >= n && isPrime(num)) {
    
                    return num;
                }
            }
        }
        return Integer.MAX_VALUE;
    }

    public long primePalindromeOdd(int n) {
    
        for (int L = 1; L <= 5; L++) {
     //  Palindrome root Number of digits L
            for (int root = (int) Math.pow(10, L - 1); root < Math.pow(10, L); root++) {
     //  Traversal digit is L All palindromes of root
                //  Odd digit palindrome string 
                StringBuilder sb = new StringBuilder(String.valueOf(root));
                for (int i = L - 2; i >= 0; i--) {
    
                    sb.append(sb.charAt(i));
                }
                long num = Long.parseLong(String.valueOf(sb));
                if (num >= n && isPrime(num)) {
    
                    return num;
                }
            }
        }
        return Integer.MAX_VALUE;
    }


    public boolean isPrime(long n) {
    
        if (n <= 2) return true;
        for (int i = 2; i <= Math.sqrt(n); i++) {
    
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
    
        Solution solution = new Solution();
        int i = solution.primePalindrome(9989900);
        System.out.println(i);
    }
}