跳转至

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