2

我在这里的这个程序有一个溢出错误！，我意识到那个程序的错误。当涉及到非常长的整数时，我不能使用 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
4

1 回答 1

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))

    不过，它并不像数学那样。

于 2013-09-02T20:46:13.693 回答