[数据结构与算法]leetcode 866. 回文素数

题目连接
思路：分解题目
思路：题目意思很明确，就一句话，让我们找到大于等于N的回文素数。
虽然就一句话，但是却有两个问题。
第一：这个数字要是大于等于N的回文数。
第二：这是数字要是素数。

那么我们先解决第一个问题，如何找大于等于N的回文数。
回文数也就是前面和后面长一个，123321， 12321，这种。

1. 那么我们看前半段就可以了，首先我们可以把N的前半段复制到后半段，也就是覆盖N的后半段。这样就可以保证得到的必定是个回文。
2. 到此，我们保证了是回文，但是却没有保证一定大于等于N，例如N=1234，复制前半段，我们得到的是1221，这是小于1234的，此时我们应该将前半段的数字加1，那么得到的必定是大于N的，相当于在N的高位进行了+1操作，肯定数字变大了，也就是将N=1234，变为1334，然后再将前半段复制到后半段。我们得到的就是1331，那么这就得到了大于等于N的回文数了。

问题一解决。
我们再来解决第二个问题，如何判断得到的这个回文数字是否是一个素数。
素数就是只有1和自身能被自身整除。
这里我们使用遍历。
我们只需要遍历2到根号n，后面的不用了，因为后面如果有因数，那么必定另一个因数会在2到根号n之间。
这样就可以判断了。
代码：

class Solution {
    
    public int primePalindrome(int n) {
        while(true){
            n = getNextPalind(n);
            if(isPrime(n)){
                return n;
            }
            //这里的+1操作别忘了。否则将有概率会出现死循环
            n++;
        }
    }

    //判断是否是素数
    public boolean isPrime(int n){
        if(n<10){
            return n==2 || n==3 || n==5 || n==7 ;
        }
        //遍历   2 ~ 根号n 内的所有数字
        for(int i = 2; i<=Math.sqrt(n); i++){
            if((n%i)==0){
                return false;
            }
        }
        return true;
    }

    //返回下一个回文
    public int getNextPalind(int n){
        char[] cs = String.valueOf(n).toCharArray();
        int mid = cs.length/2;

        while(true){
            //1 2 3
            // 将前半段复制到后半段
            for(int i = 0 ; i <mid; i++){
                cs[cs.length-1-i] = cs[i];
            }
            //将这个回文转int
            int tem = Integer.valueOf(new String(cs));

            if(tem>=n){
                //如果这个回文大于等于n 直接返回
                return tem;
            }else{
                //如果这个回文小于，那么就将这个回文的最后一个+1，但是这里要考虑最后一个是9，导致的进位
                //如果长度是奇数，那么只有中间的+1
                //如果长度是偶数，那么因为我们要处理的是前半段，所以应该是mid-1
                //上面两种情况都要处理最后一个是9的情况，考虑进位
                int t = (cs.length%2)==1 ? mid : mid-1;
                while(cs[t]=='9'){
                    cs[t--] = '0';
                }
                cs[t]++;
            }
        }
    }

    
}

这个题目的关键在于先去保证这是个大于等于N的回文，再去判断是否是素数。
如果先去找下一个素数，再去判断这个是否是回文，将会很慢，因为要找到下一个素数，很不好找，如果一直+1去找是不是素数，将会很慢，并且找到的这个素数还不一定是回文。