Primes

866. Prime Palindrome

Naively check each number from N to infinity got TLE

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            if n<=1:return False
            if n==2 or n==3:return True
            if n%2==0 or n%3==0:return False
            for i in range(5, int(n**0.5)+1, 6):
                if n%i==0 or n%(i+2)==0:return False
            return True
        for n in range(N, 2*10**8):
            s_n = str(n)
            if s_n == s_n[::-1] and is_prime(n):
                return n

Generating palindrome in a random order got TLE

from collections import deque
class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(num):
            operation=0
            if num > 1: 
                #print('********',num)
                for i in range(2, num//2+1):
                    operation += 1
                    #if i>num//2 -3:
                        #print('iiii', i)
                    #if operation>num//2-3:print(operation)
                    if num%i==0:
                        return False
                return True
            else:
                return False
def dfs():
            open_list = deque(['']+list("0123456789"))
            fin_res = []
            while open_list:
                a = open_list.popleft()
                if a and int(a)>=N and a[0]!='0' and is_prime(int(a)):
                    fin_res.append(int(a))
                for k in "0123456789":
                    new_a = k+a+k
                    if len(new_a)<8 and len(fin_res)<3:
                        open_list.append(new_a)
            #print(fin_res)
            return min(fin_res)
        return dfs()

Generating palindrome from small to large and check whether it is prime (128ms)

class Solution:
    def primePalindrome(self, N: int) -> int:
        def is_prime(n):
            if n<=1:return False
            if n==2 or n==3:return True
            if n%2==0 or n%3==0:return False
            for i in range(5, int(n**0.5)+1, 6):
                if n%i==0 or n%(i+2)==0:
                    return False
            return True
        
        def generate_palindrome(n):
            if n==1:
                for i in range(10):yield i 
            else:
                l = n//2
                begin = int('1'+'0'*(l-1))
                end = '9'*l
                if n%2==0:
                    for k in range(int(begin), int(end)+1):
                        yield int(str(k)+str(k)[::-1])
                else:
                    for  k in range(int(begin), int(end)+1):
                        for c in '0123456789':
                            yield int(str(k)+c+str(k)[::-1])
        n = len(str(N))
        while True:   
            for i in generate_palindrome(n):
                if i >=N and is_prime(i):return i
            n+=1

906. Super Palindromes

Account Login - LeetCode

https://medium.com/@jim.morris.shen/building-a-specified-patterns-28a572abdb2f?source=friends_link&sk=749f49f8fa63f1a8e50b6dc23344db85