力扣-866-回文素数

题目:
866. Prime Palindrome(medium)


解题思路:
首先取得比N大的下一个回文数,然后判断这个数是否是素数。
从这个题解获得了很多灵感。


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public int primePalindrome(int N) {
while(true){
N = nextPanlidrome(N);
if(isPrime(N)) return N;
N++;
}
}

private int nextPanlidrome(int n){
String x = n+"";
char[] s = x.toCharArray();
int length = s.length;
int mid = s.length / 2;
while(true){
for(int i = 0;i<mid;i++){//制造回文数:把前半段翻转一下复制到后半段
s[s.length - 1 -i] = s[i];
}

//判断翻转后的数是否比原数大
int temp = Integer.parseInt(new String(s));
if(temp >= n){
return temp;
}else{
//将数字增大,但要保证翻转后数字只比之前大1个数
int j = s.length % 2 == 1 ? mid : mid - 1;
while(s[j] == '9'){
s[j--] = '0';
}
s[j]++;//找到反转后最右位的数字,加一
}
}
}

private boolean isPrime(int x){
if(x <= 1) return false;
if(x == 2 || x == 3 || x == 5) return true;
for(int i = 2;i*i<=x;i++){
if(x % i == 0)
return false;
}
return true;
}