[LeetCode] 866. Prime Palindrome

[grandyang]

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 同步地址:

#866

类似题目：

Palindrome Number

Count Primes

参考资料：

https://leetcode.com/problems/prime-palindrome/

https://leetcode.com/problems/prime-palindrome/discuss/146798/Search-Palindrome-with-Odd-Digits

LeetCode All in One 题目讲解汇总(持续更新中...)