内网电脑做网站/四川seo技术培训

求出大于或等于 N 的最小回文素数。

回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是素数。

例如，2，3，5，7，11 以及 13 是素数。

回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是回文数。

例如，12321 是回文数。

示例 1：

输入：6
输出：7
示例 2：

输入：8
输出：11
示例 3：

输入：13
输出：101
 

提示：

1 <= N <= 10^8
答案肯定存在，且小于 2 * 10^8。

思路：我只想到了枚举回文串的方法过这道题，后来学习了一位大佬的题解，讲的非常清晰，学习了。

其中主要用到了两个结论：

1）更优的素数判定法：6步进素数判别法。该方法的结论是大于6的素数一定分布在6的倍数左右，我们可以将大于等于6的自然数写成6x,6x+1,6x+2,6x+3,6x+4,6x+5的形式，可以发现其中6x,6x+2,6x+3,6x+4肯定不是素数，所以素数要么是6x+1，要么是6x+5，对于小于6的数字我们单独处理即可。

2）对于一个数，若该数既是回文数，又是素数的话，该数的位数一定不是偶数，因为若位数是偶数，则一定可以被11整除。

class Solution {public int primePalindrome(int N) {int[] a=new int[] {2,2,2,3,5,5,7,7,11,11,11,11};if(N<a.length) return a[N];while(true) {int mod=N%6;String s=String.valueOf(N);if((s.length()&1)==0) {N=(int)Math.pow(10, s.length())+1;continue;}if(mod==1 || mod==5) {boolean isPrime=true,isPalindrome=true;int len1=(int)Math.sqrt(N);int len2=s.length()>>1;for(int i=5,j=0;i<=len1 || j<len2;i+=6,j++) {if(i<=len1 && (N%i==0 || N%(i+2)==0)) {isPrime=false;break;}if(j<len2 && s.charAt(j)!=s.charAt(s.length()-j-1)) {isPalindrome=false;break;}}if(isPrime && isPalindrome)return N;N=(mod==1?N+4:N+2);}elseN=(mod==0?N+1:N+(5-mod));}}
}