下一个更高的总理和回文数

一尘不染

下一个更高的总理和回文数

algorithm

关于从给定的整数中解决下一个更高的素数和回文数，是否有任何建议。

这是我正在尝试的代码段，但是它有点慢，请建议您是否有我可以测试的良好算法。

#!/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)

阅读 258

2020-07-28

共1个答案

一尘不染

您可以进行很多优化：

就像注释中建议的user2357 ..一样，请先测试回文率，然后检查数字是否为素数，因为素数检查更加昂贵。
一旦您检查数字是否可被2整除，就无需检查偶数可除性。因此，您可以将其更改[2] + range(3, int(n**0.5) + 1, 2)为仅检查2之后的奇数。（此外，您需要像我在评论中提到的那样执行sqrt + 1 ）
您应该使用()而不是[]。[]首先生成完整的因子列表，然后才检查any。如果使用()，它将创建一个生成器，因此一旦True找到一个值，它将立即停止而不计算整个列表。
出于相同原因xrange，您还应该使用而不是range（xrange给出一个生成器，range给出一个列表）
您可以使用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

This should be pretty fast for your needs I believe. But you can do the last 2
optimizations to make it much more faster if you want.

2020-07-28