Python中的回文素数

Question

我正在尝试找出两个数字之间的所有回文质数。
到目前为止，我的代码可以找到回文数，但当我检查是否是质数时，它也会打印出一些不是质数的数字。而且有些数字会被打印多次。

你能帮帮我吗？

谢谢。

a = 0
b = 500
a += 1   
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        if(i>2):
            for a in range(2,i):
                y = True
                if(i%a==0):
                    y = False
                    break
            if y:
                print(i)

Answer 1

这里有一个基于“阿特金筛法”的快速实现。我会计算出所有的质数，然后再筛选出那些是回文数的质数，前提是这些质数要大于或等于起始值。

import math
import sys

def pal_primes(start,end):
    return list(filter(lambda x: str(x)==str(x)[::-1] and x>=start, sieveOfAtkin(end)))
    
    def sieveOfAtkin(limit):
        P = [1,2,3]
        sql = int(math.sqrt(limit))
        r = range(1,sql+1)
        sieve=[False]*(limit+1)
        for x in r:
            for y in r:
                xx=x*x
                yy=y*y
                xx3 = 3*xx
                n = 4*xx + yy
                if n<=limit and (n%12==1 or n%12==5) : sieve[n] = not sieve[n]
                n = xx3 + yy
                if n<=limit and n%12==7 : sieve[n] = not sieve[n]
                n = xx3 - yy
                if x>y and n<=limit and n%12==11 : sieve[n] = not sieve[n]
        for x in range(5,sql):
            if sieve[x]:
                xx=x*x
                for y in range(xx,limit+1,xx):
                    sieve[y] = False
        for p in range(5,limit):
            if sieve[p] : P.append(p)       
        return P
    
    
    if __name__=="__main__":
        print(pal_primes(int(sys.argv[1]),int(sys.argv[2])))

这个内容是基于这个讨论：

Python中的阿特金筛法实现

Answer 2

看看我下面的代码，我们其实不需要初始化Y。使用For-Else结构就可以很好地解决问题。

a = 0
b = 500
a += 1
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        if(i>1):
            for a in range(2,i):
                if(i%a==0):
                    y = False
                    break
            else:
                print(i)

为了让答案中包含2，只需要确保检查if条件是否为(i>1)，正如@elias提到的那样。

Answer 3

请看我下面的评论：

a = 0
b = 500
a += 1
y = True
for i in range(a,b):
    if(str(i) == str(i)[::-1]):
        print (i)      # <--- You print every number that is a palindrome
        if(i>2):
            for a in range(2,i):
                if(i%a==0):
                    y = False   # <--- This never gets set back to True
                    break
            if y:
                print(i)

        i+=i   # <--- This is doing nothing useful, because it's a "for" loop

Answer 4

根据你最近的代码，你只需要确保在测试每个数字时，都要重置一下 y。这个 y 是用来判断一个数字是不是质数的正面指标。如果不重置，等你测试到数字4（第一个合成数）的时候，它的值就会一直是 False。

>>> a = 0
>>> b = 500
>>> a += 1
>>> for i in range(a,b):
        y = True
        if(str(i) == str(i)[::-1]):
            if(i>2):
                for a in range(2,i):
                    if(i%a==0):
                        y = False
                        break
                if y:
                    print(i)


3
5
7
11
101
131
151
181
191
313
353
373
383

你可以看到，这些都是质数。 你可以查看wolframalpha提供的质数列表，确保没有遗漏任何回文质数。如果你想把2也算上，就需要为它添加一个特殊的处理。