求一个素数回文数

Question

我必须在这个程序的帮助下打印第n个素数回文数，其中n是用户给出的数字，但是我在这个程序中有一个问题，因为打印答案需要花费很多时间。

n=int(input())
l=[]
for i in range(1,1000000):
y=True
if str(i)==str(i)[::-1]:
if i>=2:
for j in range(2,i):
if i%j==0:
y=False
break     
if y:
l.append(i)
print("Your Prime Palindrome Number Is:",l[n-1])

如何使这段代码节省时间?

Answer 1

这段代码的第一部分不是针对这个问题的。这是测试素数的通用策略。对于小于~500,000的值，它比sympy.isprime()更快(Intel Xeon上的Python 3.11.1)，之后的sympy版本更好地实现了这一点。

from math import sqrt, floor
def isprime(n):
if n < 2:
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, floor(sqrt(n))+1, 6):
if n % i == 0 or n % (i + 2) == 0:
return False
return True

现在您需要一些东西来测试回文。如果对象的字符串表示为回文，则此函数将返回True。

def ispalindrome(o):
return (_ := str(o)) == _[::-1]

这是程序的主要部分。因为2是唯一的偶数质数，我们把它当作一个特例。否则从3开始，只测试后面的奇数。

N = int(input('Enter value for N: '))
if N > 0:
if N == 1:
print(2)
else:
p = 3
while True:
if isprime(p) and ispalindrome(p):
if (N := N - 1) == 1:
print(p)
break
p += 2

样本输出:

Enter value for N: 11
313