python - 下一个更高的素数和回文数

Question

对于从给定的 int 求解下一个更高的素数和回文数有什么建议吗？

这是我正在尝试的代码片段，但速度有点慢，如果您有任何我可以测试的好的算法，请提出建议。

#!/usr/bin/python                                                                                                                                            

def next_higher(n):
    while True:
        s = str(n)
        if not any([n % i == 0 \
            for i in range(2, int(n**0.5))]) and s == s[::-1]:
                return n
        n = n + 1

print next_higher(2004)
print next_higher(20)

输出:

10201
101 

更新了质数前回文的代码测试。比我以前的代码快得多。 我正在执行 user2357112 的建议。

  #!/usr/bin/python                                                                                                                                          

  def next_higher(n):
      while True:
          s = str(n)
          if s == s[::-1]:
              if not any([n % i == 0 \
                  for i in range(2, int(n**0.5))]):
                      return n
          n = n + 1

  print next_higher(2004111)
  print next_higher(2004)
  print next_higher(2004)
  print next_higher(20)

Answer 1

您可以做很多优化:

• 像 user2357.. 评论中建议的那样，先测试回文，然后检查数字是否为质数，因为质数检查的成本更高。
• 一旦检查数字是否可以被 2 整除，就不需要检查偶数整除性。因此您可以将其更改为 [2] + range(3, int(n**0.5) + 1 , 2) 只检查 2 之后的奇数。(你还需要像我在评论中提到的那样执行 sqrt + 1 )
• 您应该使用 () 而不是 []。 [] 首先生成完整的因素列表，然后才检查any。如果您使用 ()，它会创建一个生成器，因此它会在找到 True 值时立即停止，而无需计算整个列表。
• 你也应该使用 xrange 而不是 range 出于同样的原因(xrange 给出了一个生成器，range给出一个列表)
• 您可以使用 Sieve of Eratosthenes显着减少素数检查所需时间的算法。
• 您还可以查看回文检查是否可以更快。实际上，您可以跳过很多数字，而不是每次只执行 + 1。

这是除了最后两个优化之外的大部分优化的版本:

def next_higher(n):
    if n % 2 == 0:
        n = n - 1
    while True:
        n = n + 2
        s = str(n)
        if s == s[::-1]:
            if not any((n % i == 0 for i in xrange(3, int(n**0.5) + 1, 2))):
                return n

我相信这应该很快就能满足您的需求。但如果您愿意，您可以进行最后 2 次优化以使其更快。