python - 动态规划 - 节省计算时间

Question

此程序出现溢出错误 here !，我意识到那个程序的错误。当涉及到非常长的整数时，我不能使用 range 或 xrange。我尝试在 Python 3 中运行该程序并且它有效。我的代码有效，但在多次后响应。因此，为了优化我的代码，我开始思考优化代码的策略。

我的问题陈述是一个数字如果它的数字之和以及它的数字的平方和是质数，则称为幸运数。 A 和 B 之间有多少个数字是幸运的？

我从这个开始:

squarelist=[0,1,4,9,16,25,36,49,64,81]

def isEven(self, n):
   return
def isPrime(n):
   return

def main():
    t=long(raw_input().rstrip())
    count = []
    for i in xrange(t):
            counts = 0
            a,b = raw_input().rstrip().split()
            if a=='1':
                    a='2'
    tempa, tempb= map(int, a), map(int,b)
    for i in range(len(b),a,-1):
       tempsum[i]+=squarelist[tempb[i]]

我想要实现的是，因为我知道系列是有序的，所以只有最后一个数字发生变化。我可以保存列表中较早数字的平方和，并继续更改最后一个数字。这不会每次都计算总和并检查平方和是否为质数。我无法将总和固定为某个值，然后继续更改最后一个数字。如何从这里继续前进？

下面提供了我的示例输入。

87517 52088
72232 13553
19219 17901
39863 30628
94978 75750
79208 13282
77561 61794

Answer 1

我根本没有得到你想要用你的代码实现的目标。这是我对这个问题的解决方案，据我所知:对于 X 范围内的所有自然数 n 使得 a < X < b 为一些自然数a、b和a < b，有多少个数n具有这样的性质:它的数字和它的十进制数字的平方和都是素数？

def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n /= 10
    return s

def sum_digits_squared(n):
    s = 0
    while n:
        s += (n % 10) ** 2
        n /= 10
    return s

def is_prime(n):
    return all(n % i for i in xrange(2, n))

def is_lucky(n):
    return is_prime(sum_digits(n)) and is_prime(sum_digits_squared(n))

def all_lucky_numbers(a, b):
    return [n for n in xrange(a, b) if is_lucky(n)]

if __name__ == "__main__":
    sample_inputs = ((87517, 52088),
                     (72232, 13553),
                     (19219, 17901),
                     (39863, 30628),
                     (94978, 75750),
                     (79208, 13282),
                     (77561, 61794))

    for b, a in sample_inputs:
        lucky_number_count = len(all_lucky_numbers(a, b))
        print("There are {} lucky numbers between {} and {}").format(lucky_number_count, a, b)

一些注意事项:

• is_prime 是最简单的实现方式。对于样本输入来说，它仍然足够快。有许多更好的实现可能(而且只需要一个谷歌)。最明显的改进是跳过除 2 以外的所有偶数。仅此一项就能将计算时间缩短一半。
• 在 Python 3 中(我真的推荐使用它)，记得使用 //= 强制除法结果为整数，并使用 range而不是 xrange。此外，加速 is_prime 的一种简单方法是 Python 3 的 @functools.lru_cache。 .

• 如果你想保存一些行，通过将它们转换为 str 然后返回到 int 来计算数字的总和:

  def sum_digits(n):
      return sum(int(d) for d in str(a))
  

  不过，它不是数学。