866. Prime Palindrome

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

类似题目:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation