python88分求助

P1217 [USACO1.5] 回文质数 Prime Palindromes

Xuuuuu @ 2024-02-04 18:40:54

a,b=map(int,input().split())
l = len(list(str(b)))
used = [0]*(l+5)
ans = []
import math
def isprime(x):
    if x==0 or x==1:
        return False
    for i in range(2,int(math.sqrt(x))+1):
        if not x%i:
            return False
    return True
def dfs(k):
    global ans
    if k*2-1>l:
        return
    else:
        for i in range(0,10):
            used[k]=i
            u1 = used[1:1+k] # 123
            u2 = u1[::-1] # 321
            u2 = u2[:-1] # 32
            u2.extend(u1) # 32123
            u = list(map(str,u2))
            u = ''.join(u)
            u = int(u)
            if isprime(u) and u<=b and u>=a:
                ans.append(u)
            dfs(k+1)
dfs(1)
if 11>=a and 11<=b:
    ans.append(11)
ans.sort()
for x in ans:
    print(x)

最后一个点TLE,不知道哪里还能剪枝


by White_Falcon @ 2024-02-04 18:42:52

小技巧:先用朴素算法TLE把表达出来再直接输出


by White_Falcon @ 2024-02-04 18:43:05

@Xuuuuu


|