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

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次优化,使其更快.