Find the smallest prime palindrome greater than or equal to N.
Recall that a number is prime if it’s only divisors are 1 and itself, and it is greater than 1.
For example, 2,3,5,7,11 and 13 are primes.
Recall that a number is a palindrome if it reads the same from left to right as it does from right to left.
For example, 12321 is a palindrome.
Example 1:
Input: 6
Output: 7
Example 2:
Input: 8
Output: 11
Example 3:
Input: 13
Output: 101
Note:
1 <= N <= 10^8- The answer is guaranteed to exist and be less than
2 * 10^8.
这道题给了我们一个整数N，让找一个大于等于N的回文质数，既要求是质数，又要求是回文数。其实这道题可以当作两道题揉到了一起，判断质数和回文数分别可以当作单独的题。没想太多，博主上来就准备暴力搜索，先写两个子函数，分别用来判断质数和回文数，然后就直接从N开始搜索了，对每个数字都分别调用判断质数和回文数的子函数，若都满足，则返回该数即可。理想是丰满的，现实是骨感的，OJ 教你做人系列之 TLE 超时！想着优化一下吧，直接跳过所有的偶数吧（2除外），还是跪。看来小优化是行不通，得大改。
问题出现在哪里了呢？肯定是判断质数和回文数的子函数太占时间了，怎么优化呢？对于质数来说，非常的不规则，没有太好的办法来直接组成质数，而是需要通过验证来看其是否为质数。而回文数就不一样的，非常的有特点，我们可以直接按规律来组成回文数，而不是对每个数字都进行验证，这样的话就相当于去掉了验证回文数的步骤，是一个相当大的提升。怎么拼接呢？由于给了N的取值范围，我们可以遍历前一半的所有数字，然后翻转一下，组成后一半，两个拼起来就是回文数了。但问题又来了，回文数的长度是分奇偶的，长度为奇数的回文数，最中间的数字是没有对应的，肿么办？其实这道题挺考数学知识的，用到了一个比较偏门的定理，就是所有长度为偶数的回文数字一定是 11 的倍数。博主表示从没听过这个定理，证明过程请参见 lee215 大神的帖子。通过这个定理，可以知道除了11之外，所有长度为偶数的回文数都不是质数，那么当N为 [8, 11] 中的数字时，才会返回11，这个就当 corner cases 提前判断了，对于其他所有的都是符合规律的。那就可以只组奇数的回文数了，由于N的范围是 [1, 1e8]，所以前一半范围是 [1, 1e5)，因为还包含了最中间的那个数字，所以在翻转之后，记得要把第一位数字去掉，因为最中间的数字只能保留一个，然后把两个数字拼接起来。此时再判断这个拼接后的数字是否大于等N，并且是否是质数，都满足的话返回这个数字即可，参见代码如下：
class Solution {
public:
int primePalindrome(int N) {
if (N >= 8 && N <= 11) return 11;
for (int i = 1; i < 1e5; ++i) {
string s = to_string(i), t(s.rbegin(), s.rend());
int x = stoi(s + t.substr(1));
if (x >= N && isPrime(x)) return x;
}
return -1;
}
bool isPrime(int num) {
if (num < 2 || num % 2 == 0) return num == 2;
int limit = sqrt(num);
for (int i = 3; i <= limit; ++i) {
if (num % i == 0) return false;
}
return true;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/866
类似题目：
参考资料：
https://leetcode.com/problems/prime-palindrome/
https://leetcode.com/problems/prime-palindrome/discuss/146798/Search-Palindrome-with-Odd-Digits
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
