LeetCode866. 回文素数Python実現

分析:题目は时间を节约するため、Nの位数が偶数の时、それでは11を除いてその他はすべて素数ではありませんて、ネット上でその他の证明があります.1001の桁数が4の場合、次に10001から始めるべきで、1001-9999で素数がないので(これは10001から時間を節約するため)、具体的にはN=pow(10,Nの桁数)+1を実現して、注意して取ります!

import math
import copy


class Solution:
    def primePalindrome(self, N):
        """
        :type N: int
        :rtype: int
        """
        while True:
            if N in [2, 3, 5, 7, 11]:
                return N
            elif N == 1:
                return 2
            
            if N > 31880255: #           ，               100030001
                return 100030001
            if (N > 11) and (len(str(N)) % 2 == 0):
                N = int(pow(10, len(str(N)))) + 1
                continue
            flag1 = self._isPalindrome(N)

            if flag1:
                a = math.ceil(math.sqrt(N))
                flag = self._isSushu(N, a)
                if flag:
                    return N
             
            if N % 2 != 0:
                N = N + 2
            else:
                N = N + 1

    def _isSushu(self, N, end):
        flag = False
        if N % 2 == 0:
            return flag
        for i in range(3, end + 1):
            if i % 2 != 0:
                if N % i != 0:
                    flag = True
                else:
                    flag = False
                    break
        return flag

    def _isPalindrome(self, N):
        if N % 2 == 0:
            return False
        s = list(str(N))

        s2 = copy.deepcopy(s)
        s2.reverse()
        if s == s2:
            return True
        else:
            return False


s = Solution()
import time
t1 = time.time()
print(s.primePalindrome(31880255))
print(time.time() - t1)