下一个较高的质和回文数 [英] Next higher prime and palindrome number

问题描述

有没有从一个给定的int解决下一个更高的质和回文数的任何建议。

下面的代码片段，我想，但它是一种缓慢的，请建议，如果你已经什么好的算法，我可以测试。

 ＃！的/ usr / bin中/蟒蛇

高清next_higher（N）：
    而真正的：
        S = STR（N）
        如果没有任何（[N％我== 0 \
            因为我在范围内（2，INT（N ** 0.5））]）和S == S [::  -  1]：
                返回否
        N = N + 1

打印next_higher（2004）
打印next_higher（20）
 

输出：

  10201
101
 

在黄金面前回文更新code测试。比我的previous code快得多。 我从user2357112实施的建议。

 ＃！的/ usr / bin中/蟒蛇

  高清next_higher（N）：
      而真正的：
          S = STR（N）
          如果s == S [::  -  1]：
              如果没有任何（[N％我== 0 \
                  因为我在范围内（2，INT（N ** 0.5））]）：
                      返回否
          N = N + 1

  打印next_higher（2004111）
  打印next_higher（2004）
  打印next_higher（2004）
  打印next_higher（20）
 

解决方案

有相当多的优化，你可以这样做：

• 在像user2357 ..建议的意见，测试palindromeness，然后再检查数量为素数，因为主要检查比较昂贵。
• 您不需要一旦你检查的次数是2整除所以，你可以把它改成 [2] +系列（3，INT（N检查偶数整除** 0.5 ）+ 1，2） 2。检查后，仅奇数（另外你需要做的开方+ 1像我在评论中提到的）
• 您应该使用（），而不是的[] 。 [] 生成要素的整个列表第一个也是唯一然后检查任何。如果你使用（），它创造了一个发电机，所以只要不计算找到了真值停止整个列表。
• 您还应该使用的xrange 而不是范围出于同样的原因（的xrange 给出了一个发电机，范围给出一个列表）
• 您可以使用埃拉托色尼算法筛显著减少采取素数检查时间
• 您也可以看到，如果回文检查可以做出更快。实际上，你可以跳过+ 1 每次都做只是的一大堆数字来代替。

下面是一个版本，与大多数这些优化，除了最后两个：

 高清next_higher（N）：
    如果n％2 == 0：
        N = N  -  1
    而真正的：
        N = N + 2
        S = STR（N）
        如果s == S [::  -  1]：
            如果没有任何（（N％我== 0我的xrange（3，INT（N ** 0.5）+ 1,2）））：
                返回否
 

这应该是pretty的快速满足您的需求，我相信。但是你可以做的最后一2的优化，使其如果你想要更多更快。

Is there any suggestion on solving next higher prime and palindrome number from a given int.

Here is the snippet I am trying but its a kind of slow, please suggest if you ve any good algorithm that i can test.

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

Output:

10201
101 

Updated code testing for palindrome before prime. much faster than my previous code. I am implementing the suggestion from 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)

解决方案

There are quite a few optimizations you could do:

• Like user2357.. suggested in the comments, test palindromeness first, and then check if the number is prime, since prime check is more expensive.
• You don't need to check even number divisibility once you check is the number is divisible by 2. So you can change it to [2] + range(3, int(n**0.5) + 1, 2) to check only odd numbers after 2. (Also you need to do sqrt + 1 like I mentioned in the comments)
• You should use () instead of []. [] generates the entire list of factors first and only then checks for any. If you use (), it creates a generator, so it stops as soon as a True value is found without calculating the entire list.
• You should also use xrange instead of range for the same reason (xrange gives a generator, range gives a list)
• You can use the Sieve of Eratosthenes algorithm to significantly reduce the time taken for prime number check.
• You can also see if the palindrome check can be made faster. You can actually skip a whole lot of numbers instead of doing just + 1 each time.

Here is a version with most of these optimizations except the last two:

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.

这篇关于下一个较高的质和回文数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！