[算法]回文素数——LeetCode.866

题目链接  啊，又是一道有些恶心的题目，轻看上去分分钟暴力秒的感觉，但是很显然分分钟样例卡爆你

总之，在了解了如何骗样例的同时，优化的过程也是漫长到你恶心，恶心了我大概一个下午加晚上的时间= =

思路

显然先来两个函数分别判断是否是素数以及是否回文，回文的问题不大，一开始我用的StringBuffer，直接将int转字符然后用自带的reserve函数即可，或者按照分位取值的方法，如下：

while (a > 0) {
            ans = 10 * ans + (a % 10);
            a /= 10;
        }

素数这边的话也是常规的遍历，一开始只记得√N的方法，即一个数的因数必定是成对，其中一个必定小于或等于该数的平方根，照例这么一敲，妥妥超时，其实主要是卡大样例9989900.。。期间各种优化跳数，最后发现这个样例给的也很有意思 位数为8的数不可能是素数，跳过了1kw个数。。。

题解代码

package com.leaf;

//暴力解不可行
//==打表
//跳过位数8

public class PrimePalindrome {

public static void main(String[] args) {
System.out.println(primePalindrome(9989900));
}

public static int primePalindrome(int N) {
int lim = 200000000;

while(N<lim) {
if(judgeF(N)&&judgeS(N)) {
return N;
}
N++;
if(String.valueOf(N).length()==8 ) {
N=100000000;
}
}
return N;
}

public static boolean judgeF(int a) {
int num = a;
if(a<2) {
return false;
}

if(a>11&&String.valueOf(a).length()%2==0) {
return false;
}
if(a>=4&&a%6!=1&&a%6!=5) { // 不在6的倍数两侧的一定不是质数
return false;
}
if(a>=100) {
num = (int) Math.sqrt(a); //+1避免平方数
for(int i=2;i<=num;i++) {
if(a%i==0) {
return false;
}
}
}
return true;
}

public static boolean judgeS(int a) {
// StringBuffer te = new StringBuffer(String.valueOf(a));
// if(te.toString().equals(te.reverse().toString())) {
// return true;
// }else {
// return false;
// }
int ans = 0;
int aa = a;
while (a > 0) {
ans = 10 * ans + (a % 10);
a /= 10;
}
if(aa==ans) {
return true;
}else {
return false;
}
}

}

官方题解代码：

class Solution {
public int primePalindrome(int N) {
while (true) {
if (N == reverse(N) && isPrime(N))
return N;
N++;
if (10_000_000 < N && N < 100_000_000)
N = 100_000_000;
}
}

public boolean isPrime(int N) {
if (N < 2) return false;
int R = (int) Math.sqrt(N);
for (int d = 2; d <= R; ++d)
if (N % d == 0) return false;
return true;
}

public int reverse(int N) {
int ans = 0;
while (N > 0) {
ans = 10 * ans + (N % 10);
N /= 10;
}
return ans;
}
}

当然，还有一种特殊的方式：打表法

即构造符合要求的回文素数，放到一个LinkedList里，然后遍历即可，显然速度快开销小，但是有种钻空子的感觉23333

心得

来回顾一下素数查找的一些常用的数学结论

1.  1不是素数，考虑一个数是否为素数，只需要从2开始到√N之间是否有能整除N的数，因为一个数的因数必定成对，且每对中较小的那个小于等于√N，较大的那个大于等于√N（等于存在恰好N为平方数）。
2. 所有大于3的素数都在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的倍数的左右的。
3. 位数为8的数都不是素数。