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

Question

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

这是我正在尝试的片段，但有点慢，请建议你是否有我可以测试的好算法。

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

更新了prime之前的回文代码测试。比我以前的代码快得多。我正在执行用户2357112的建议。

  #!/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）
• 您应该使用()而不是[]。CCD_ 4首先生成整个因素列表，然后才检查CCD_。如果使用()，它会创建一个生成器，因此一旦找到True值，它就会停止，而不计算整个列表
• 出于同样的原因，您也应该使用xrange而不是range（xrange给出生成器，range给出列表）
• 您可以使用埃拉托斯特内斯筛算法来显著减少素数检查所需的时间
• 您还可以查看是否可以更快地进行回文检查。实际上，你可以跳过很多数字，而不是每次只做+ 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

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

Answer 2

除了已经提出的建议之外，

我建议你首先得到第一个回文数，它刚好高于给定的整数。

你可以试着把中间的数字向外匹配。

此外，你应该只检查奇数位数的数字，因为如果一个数字有偶数位数，并且是回文，那么它总是可以被11整除，不能是素数。

一旦你得到了第一个有奇数位数的回文数，并且刚好高于当前数字，测试它的素性，然后找到下一个高于这个的回文数字。

你可以通过增加中间的数字来做到这一点。

继续这样做，直到它滚到零。在这种情况下，开始递增两个相邻的数字。

继续，直到你达到一个素数。

Answer 3

我尝试优化回文检查，即查找奇数回文。由于第一个数字应该是奇数，所以我把重点放在了这一部分。这是下面的代码，假设它大于1位。

def next_odd_palindrome(n):
  """to check the next odd palindrome number"""
  if n%2==0:
    n=n-1
  while True:
    n=n+2
    s = str(n)
    if int(s[0])%2==0:
      n = int(str(int(s[0])+1)+ s[1:])
      s = str(n)
    if s==s[::-1]:
      return n

如果有什么问题，请告诉我。

Answer 4

为了好玩，我实现了Hari Shankar和Abhishek Bansal的所有优化。

它首先找到奇数长度较高的回文，然后以保持其回文性的方式递增回文。然后使用开始时通过筛法计算的素数来检查每个数字。

在我的电脑=D 中，这可以在1秒内处理多达n=10^14（如果你增加CACHE大小，可以更高）

primes = []
CACHE = int(10**7) # Cache size for Sieve
# Custom class for immediate printing of output
import sys
class Unbuf:
    def __init__(self,stream):
        self.stream = stream
    def write(self,data):
        self.stream.write(data)
        self.stream.flush()
sys.stdout = Unbuf(sys.stdout)
def sieve():
    global primes
    is_prime = [False,False]+([True]*(CACHE-1))
    for i in xrange(2,int(CACHE**0.5)):
        if is_prime[i]:
            is_prime[i*i::i] = [False]*((CACHE-i*i+i)/i)
    primes = [num for num, bool_prime in enumerate(is_prime) if bool_prime]
def is_prime(n):
    """Checks whether n is prime"""
    global primes
    if n<2:
        return False
    if n==2:
        return True
    for prime in primes:
        if prime>n**0.5+1:
            return True
        if n%prime==0:
            return False
    # For the case that the number is bigger than the square of our largest prime
    for num in xrange(primes[-1]+2,n**0.5+1,2):
        if n%num==0:
            return False
    return True
def next_higher_odd_length_palindrome(n):
    n = str(n)
    if len(n)%2==0: # Even length, take the smallest odd length (10(00)*1)
        n = '1'+('0'*(len(n)-1))+'1'
    else:
        middle_idx = len(n)/2
        left = int(n[:middle_idx+1])
        left_cmp = n[middle_idx::-1]
        right_cmp = n[middle_idx:]
        # If mirroring left part to right part
        # makes the number smaller or equal, then
        if right_cmp>=left_cmp:
            # Increase the left half number
            left = left+1
        # Mirror left part to the right part
        n = str(left)+str(left)[-2::-1]
    return n
def next_higher(n):
    if n<=1:
        return 2
    # Ensure the number is a palindrome of odd length
    n = next_higher_odd_length_palindrome(n)
    while True:
        if is_prime(int(n)):
            return int(n)
        n = next_higher_odd_length_palindrome(n)
        if int(n[0])%2==0:
            new_lead = str(int(n[0])+1)
            n = new_lead+n[1:-1]+new_lead
import time
print 'Sieving...',
start_time = time.time()
sieve()
print 'Done in %.3fs' % (time.time() - start_time)
print next_higher(2004111)
print next_higher(2004)
print next_higher(20)
while True:
    n = int(raw_input('Enter n: '))
    start_time = time.time()
    result = next_higher(n)
    print 'Next higher prime palindrome: %d (calculated in %.3fs)' % (result, time.time() - start_time)

在我的计算机中，哪个输出：

正在筛选。。。1.444秒内完成300700310301101输入n:199999999次高素数回文：10000500001（以0.004计算）输入n:199999999999次高素数回文：3000002000003（以0.051s计算）输入n：1000000000000下一个更高的素数回文：10000008000001（以0.030s计算）输入n: