866.Prime Palindrome
866.回文素数
求出大于或等于 N 的最小回文素数。 回顾一下,如果一个数大于 1,且其因数只有 1 和它自身,那么这个数是素数。 例如,2,3,5,7,11 以及 13 是素数。 回顾一下,如果一个数从左往右读与从右往左读是一样的,那么这个数是回文数。 例如,12321 是回文数。
方法,先定义两个函数,一个求回文,一个判断素数。 难点在于超时问题,当n大于11,且n的位数为偶数时,n不可能为回文素数,因此为了缩减时间,将偶数位回文数加一个数量级。
1
class Solution {
2
public:
3
int primePalindrome(int N) {
4
if(N<=2)
5
return 2;
6
if(N%2 ==0 )
7
N++;
8
while(true)
9
{
10
if(N > 11 && (int)log10(N)%2)
11
N = pow(10,(int)log10(N)+1)+1;
12
if(reverse(N) == N && palin(N) )
13
return N;
14
N +=2;
15
}
16
return -1;
17
18
}
19
private:
20
int reverse(int n)
21
{
22
int tmp=0;
23
while(n)
24
{
25
tmp = 10*tmp + n%10;
26
n /=10;
27
}
28
return tmp;
29
}
30
int palin(int n)
31
{
32
int tmp=sqrt(n);
33
for (int i=2; i<=tmp;i++)
34
if(n%i==0)
35
return 0;
36
return 1;
37
}
38
};
Copied!
Copy link