LeetCode: 866. 回文素数¶
1、题目描述¶
求出大于或等于 N 的最小回文素数。
回顾一下，如果一个数大于 1，且其因数只有 1 和它自身，那么这个数是*素数*。
例如，2，3，5，7，11 以及 13 是素数。
回顾一下，如果一个数从左往右读与从右往左读是一样的，那么这个数是*回文数。*
例如，12321 是回文数。
示例 1：
输入：6 输出：7
示例 2：
输入：8 输出：11
示例 3：
输入：13 输出：101
提示：
1 <= N <= 10^8
2、解题思路¶
这道题的基本思路就是，构造不小于N的回文数，判断是不是质数，如果是，就返回
关键点在于构造回文数
这里使用的是回文长度的思路
例如现在构造3位的回文数，基准值是10，第一个回文就是101
然后是111
如果构造4位的回文，基准值是10，第一个回文是1001，第二个是1111，以此类推
import math
class Solution:
def primePalindrome(self, N):
"""
:type N: int
:rtype: int
"""
p = str(N)
p_length = len(p)
base_num = 10 ** ((p_length - 1) // 2)
if base_num == 1:
base_num = 0
while True:
judge_num = self.buildPalindrome(base_num, p_length)
if judge_num >= N:
if self.isPrime(judge_num):
return judge_num
if len(str(base_num + 1)) > len(str(base_num)):
p_length += 1
base_num = 10 ** ((p_length - 1) // 2)
else:
base_num += 1
def buildPalindrome(self, num, p_length):
s = str(num)
if p_length % 2 == 0:
result = int(s + "".join(list(reversed(s))))
else:
result = int(s[:-1] + s[-1] + "".join(list(reversed(s[:-1]))))
return result
def isPrime(self, num):
if num <= 1:
return False
if num == 2:
return True
a = math.ceil(math.sqrt(num))
for i in range(2, a + 1):
if num % i == 0:
return False
return True