Leetcode.866 回文质数

题目链接

Leetcode.866 回文质数 rating : 1938

题目描述

给你一个整数 $n$ ，返回大于或等于 $n$ 的最小 回文质数。

一个整数如果恰好有两个除数：$1$ 和它本身，那么它是 质数 。注意，$1$ 不是质数。

• 例如，$2、3、5、7、11$ 和 $13$ 都是质数。

一个整数如果从左向右读和从右向左读是相同的，那么它是 回文数 。

• 例如，$101$ 和 $12321$ 都是回文数。

测试用例保证答案总是存在，并且在 $[2,2\times 10^8]$ 范围内。

示例1：

输入：n = 6
输出：7

示例2：

输入：n = 8
输出：11

示例3：

输入：n = 13
输出：101

提示：

• $1\le n\le 10^8$

解法：数学 + 判断质数

对于 回文数 ，我们可以得出这么一个结论：任何一个大于 $11$ 的偶数长度的回文数，一定是 $11$ 的倍数。

证明如下：

• $10^0=1mod11=1$
• $10^1=10mod11=10$
• $10^2=100mod11=1$
• $10^3=1000mod11=10$
• $10^4=10000mod11=1$
• …

根据数学归纳法，我们可以得出这样的结论：

• $n$ 为偶数，那么 $10^{n}mod11=1$
• $n$ 为奇数，那么 $10^{n}mod11=10$

假设回文数 $P$ 一共有 $2n$ 位，从高到低分别为 $a_1{a}_2{a}_3{a}_4...a_n{a}_n{a}_{n-1}...a_2{a}_1$。

将其转换为十进制的形式如下：

$$P=a_1\times 10^{2n-1}+a_2\times 10^{2n-2}+...+a_n\times 10^n+a_n\times 10^{n-1}+...+a_2\times 10+a_1$$

如果对回文数 $P$ 模 $11$，我们可以得到如下的结果：

$$P=a_1\times 10+a_2\times 1+a_3\times 10+...a_n\times 10+a_n\times 1+...+a_2\times 10+a1$$

将其整理一下得到如下结果：
$$P=a_1\times 11+a_2\times 11+a_3\times 11+...+a_n\times 11$$

可以发现在对 $P$ 模 $11$ 的基础之上，剩下的余数依旧是 $11$，说明 $11$ 可以整除 $P$，也就是 $P$ 是 $11$ 的倍数。

根据以上的证明，我们可以得出结论：

• 如果 $n\le 11$，那么只需要在 $[2,11]$ 中找到第一个大于等于 $n$ 的质数返回即可。
• 如果 $n>11$，因为偶数长度的回文数全都不是质数，所以我们只需要判断奇数长度的回文数。由于是回文数，所以我们只需要获取前一半，后一半直接拼接上即可。所以只需要在 $[10,19999]$ 找到第一个大于等于 $n$ 的回文质数 $x$ 即可。

时间复杂度：$O(n^{\frac{3}{4}})$

C++代码：

class Solution {
public:bool check(int x){if(x < 2) return false;for(int i = 2;i * i <= x;i++){if(x % i == 0) return false;}return true;}int primePalindrome(int k) {if(k <= 11){for(int i = 2;i <= 11;i++){if(i >= k && check(i)) return i;}}else{for(int i = 10;i <= 19999;i++){string s = to_string(i);int n = s.size();for(int i = n - 2;i >= 0;i--) s.push_back(s[i]);int x = stoi(s);if(x >= k && check(x)) return x;}            }return -1;}
};

Python3代码:

def check(x: int) -> bool:if x < 2:return Falsei = 2while i * i <= x:if x % i == 0:return Falsei += 1return Trueclass Solution:def primePalindrome(self, k: int) -> int:if k <= 11:for i in range(2, 12):if i >= k and check(i):return ielse:for i in range(10, 20000):s = str(i)n = len(s)s = s + s[:n - 1][::-1]x = int(s)if x >= k and check(x):return xreturn -1