如何在 Python 3 中生成素数回文

Question

我正在尝试生成两个整数（由用户给定）之间的素数回文，但根本无法弄清楚哪里出错了。请问有人可以解释一下吗？

这是我目前得到的：

#Palindrome test
def palindrome(num):
    str(num) == str(num)[::-1]

#Prime test (excl. 3, 5 & 7 because not palindrome)
def prime(num):
    abs(num)%2 != 0
    abs(num)%3 != 0
    abs(num)%5 != 0
    abs(num)%7 != 0


N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

for x in range(N, M):
    if palindrome(x) and prime(x):
        print(x)

好的，正如所指出的那样 - 上面的代码中存在不止一个问题。我再次尝试并想出了这个（如下），它设法打印出所有回文，但也包括非素数。我哪里错了？

N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

def palindrome(num):
    return str(num) == str(num)[::-1]

def prime(x):
    for x in range(N, M+1):
        for y in range(2, x):
            if x%y != 0:
                return True

for z in range(N, M):
    if palindrome(z) and prime(z):
        print(z)

感谢到目前为止的所有反馈！

Answer 1

看看这是否有效

#Palindrome test
def palindrome(num):
    return str(num) == str(num)[::-1]

#Prime test (excl. 3, 5 & 7 because not palindrome)
def prime(num):
    if abs(num)%2 != 0 and abs(num)%3 != 0 and abs(num)%5 != 0 and  abs(num)%7 != 0:
        return True
    return False

顺便说一句 - 143 不是素数，但您的素数测试会 return 为真。不确定这是否是设计使然。

编辑：是的，我知道素数测试不正确。我只是按照他使用的方式采用了 OP 的代码。

尝试使用它来检查素数

def prime(int x):
    if x < 0: x *= -1
    i = 2
    while i*i <= x:
        if x % i == 0: return False
        i += 1
    return True

Answer 2

我进一步 @Banach 代码。素数测试已更改，以适应可被素数本身整除的数字。灵感来自 here。

素数测试现在也适用于更大的数字。

演示代码

#Palindrome test
def palindrome(num):
    return str(num) == str(num)[::-1]

#Prime Test
def is_prime(n):
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int(n**0.5)
  f = 5
  while f <= r:    
    if n%f == 0: return False
    if n%(f+2) == 0: return False
    f +=6
  return True

#Get user input
N = int(input("Enter the start point N: "))
M = int(input("Enter the end point M: "))

for x in range(N, M):

    #Check for palindrome and prime number
    if palindrome(x) and is_prime(x):

        #Omitting 2,3,5,7 as per request
        if abs(x)%2 != 0 and abs(x)%3 != 0 and abs(x)%5 != 0 and  abs(x)%7 != 0:
            print(x)

输出

Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win32
Type "copyright", "credits" or "license()" for more information.
>>> ================================ RESTART ================================
>>> 
Enter the start point N: 2
Enter the end point M: 20000
11
101
131
151
181
191
313
353
373
383
727
757
787
797
919
929
10301
10501
10601
11311
11411
12421
12721
12821
13331
13831
13931
14341
14741
15451
15551
16061
16361
16561
16661
17471
17971
18181
18481
19391
19891
19991
>>>

Answer 3

这似乎是一个有趣的问题。如果你有像 Miller Selfridge Rabin 素数测试这样的工业强度测试，你可以找到一些真正的大例子（尽管得到复合的概率微乎其微）：

import random

#The following function finds s and d in
#n-1 = 2^s*d with d odd

def findSD(n):
    s = 0
    d = n-1
    while d % 2 == 0:
        s = s + 1
        d = d//2
    return s,d

def checkBase(a,n):
    s,d = findSD(n)
    x = pow(a,d,n)
    if x == 1 or x == n-1:
        return "probable prime"
    else:
        for i in range(s-1):
            x = pow(x,2,n)
            if x == 1:
                return "composite"
            elif x == n-1:
                return "probable prime"
        #if you get to this stage, -1 not reached despite s-1
        #squarings -- so must be composite
        return "composite"

def MSR(n,k):
    #tests if an odd number is prime
    for i in range(k):
        a = random.randint(2,n-2)
        if checkBase(a,n) == "composite":
            return "composite"
    #if you get here n has survived k potential witnesses, so
    return "probable prime"

def prime(n):
    smallPrimes = [2,3,5,7,11,13,17,19]

    for p in smallPrimes:
        if n == p:
            return True
        elif n % p == 0:
            return False

    if MSR(n,20) == "composite":
        return False
    else:
        return True

def randOddPalindrome(n):
    digits = [random.choice('13579')]
    if n > 1:
        m = (n-2)//2
        digits.extend(random.choice('0123456789') for i in range(m))
        digit = [''] if n%2 == 0 else [random.choice('0123456789')]
        digits += (digit + digits[::-1])
    return int(''.join(digits))

def findPrimePalindrome(n,trials = 10000):
    for i in range(trials):
        p = randOddPalindrome(n)
        if prime(p): return p
    return "No primes found in " + str(trials) + " trials"

例如，

>>> findPrimePalindrome(5)
30803
>>> findPrimePalindrome(6)
'No primes found in 10000 trials'
>>> findPrimePalindrome(101)
10411470210071416936952003803463770311632555360794349706355523611307736430830025963961417001207411401

当我看到 n=6 的输出时，我一度怀疑是一个错误，但后来意识到 11 是 唯一的 素数回文，因为所有回文都是偶数位数是11的倍数

如何在 Python 3 中生成素数回文

How to generate prime palindromes in Python 3

python

palindrome

python-3.x