Python中的回文/素数检查器无法工作

Question

我的任务是这样的：

什么是唯一一个（两位数或以上的）既在二进制（基数2）又在十进制（基数10）中都是回文的质数？

每当我运行这段代码时，什么都没有发生，它就像进入了无限循环。我哪里做错了，或者我该如何改进？非常感谢大家的帮助。

def isPrime(n):
    if type(n) != int or n <= 1:
        return False
    elif n == 2:
        return True
    elif n%2 == 0:
        return False
    else:
        for x in range(2, int(n**0.5)+1):
            if n%x == 0:
                return False
                break
        return True
def isPalindrome(x):
    num = str(x)[::-1]
    if str(x) == num:
        return True
    else:
        return False
while True:
    a = 11
    if isPrime(a) and isPalindrome(a) == True:
        if isPalindrome(bin(a)) == True:
            print a
            break
    else:
        a+=2
        print a

--------- 编辑：**已解决** ---------

修改后的代码：

def isPrime(n):
    if n < 2 or n%2 == 0:
        return False
    if n == 2:
        return True
    else:
        for x in range(3, int(n**0.5)+1, 2):
            if n%x == 0:
                return False
        return True
def isPalindrome(x):
    num = str(x)[::-1]
    return str(x) == num
a = 11
while True:
    if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, "b")):
            print a
            break
    a+=2

感谢所有提供答案的人。

Answer 1

bin()的输出结果永远不会是回文，因为它前面会加上0b这两个字符：

>>> bin(3)
'0b11'
>>> isPalindrome(bin(3))
False

你可以把这两个字符切掉，或者用format()来生成一个二进制的表示：

>>> format(3, 'b')
'11'
>>> isPalindrome(format(3, 'b'))
True

你的循环还有一个问题：如果你找到了一个在二进制下不是回文的质数，它就不会增加：

if isPrime(a) and isPalindrome(a) == True:
    if isPalindrome(format(a, 'b')) == True:
        print a
        break
    # no else here
else:
    a+=2
    print a

只需在一个测试中检查所有条件即可：

if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, 'b')):
    print a
    break
a += 2

在布尔测试中，几乎不需要测试== True。

接下来是你在循环中重置了a：

while True:
    a = 11

在循环的其他部分你对a做什么都没关系，循环开始时它会回到11。把这部分移到循环外：

a = 11
while True:
    if isPrime(a) and isPalindrome(a) and isPalindrome(format(a, 'b')):
        print a
        break
    a += 2

每当你写if comparison: return True后面接else: return False时，直接返回测试结果就行：

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

因为==比较运算符已经返回一个布尔值了。

你的质数测试其实不需要检查n的类型（因为你只会传入整数），但正确的检查类型的方法是使用：

isinstance(n, int)

这样也能兼容int的子类。即使你确实需要限制某个东西为特定类型而不允许子类，你也会使用：

type(n) is int

因为类型是单例。

参考Python语言的isPrime函数，如果你使用：

def isPrime2(n):
    if n < 2: return False
    if n == 2: return True
    for i in range(3, int(n ** 0.5) + 1, 2):   # only odd numbers
        if n % i == 0:
            return False
    return True

你的isPrime()函数会稍微快一点。

通过限制你查看的值的数量，可以让你的循环更高效。如果你查看OEIS上的回文质数系列，你会发现除了11以外，所有十进制的回文质数都是奇数位数，所以你可以跳过很多数字。以下代码会产生更好的候选：

def palindromic_candidates():
    yield 11
    outer = 1
    while True:
        for i in range(10):
            yield int('{}{}{}'.format(outer, i, str(outer)[::-1]))
        outer += 1

演示：

>>> from itertools import islice
>>> pc = palindromic_candidates()
>>> list(islice(pc, 30))
[11, 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, 202, 212, 222, 232, 242, 252, 262, 272, 282, 292, 303, 313, 323, 333, 343, 353, 363, 373, 383]
>>> list(islice(pc, 100, 130))
[13931, 14041, 14141, 14241, 14341, 14441, 14541, 14641, 14741, 14841, 14941, 15051, 15151, 15251, 15351, 15451, 15551, 15651, 15751, 15851, 15951, 16061, 16161, 16261, 16361, 16461, 16561, 16661, 16761, 16861]

用这个替代你的while True循环，去掉a += 2这一行：

for a in palindromic_candidates():
    if isPrime(a) and isPalindrome(format(a, 'b')):
        print a
        break

在这里你可以省去对十进制回文的测试，因为生成器只会产生回文。