我是否已检查此列表的每个连续子集？

Question

我正试图在Project Euler上解决问题50 .不要给我答案或为我解决,只是试着回答这个具体问题.

目标是找到连续素数的最长和,这些素数会增加到低于一百万的素数.我写了一个筛子来找到n下面的所有素数,我已经确认它是正确的.接下来,我将使用以下方法检查连续素数的每个子集的总和:

我有一个空列表sums.对于每个素数,我将它添加到每个元素中sums并检查新的总和,然后我将素数追加到sums.

这是在python中

primes = allPrimesBelow(1000000)
sums = []
for p in primes:
    for i in range(len(sums)):
        sums[i] += p
        check(sums[i])
    sums.append(p)

我想知道我是否已经要求check()两个或更多连续素数的总和低于一百万

问题是有一个素数,953,可以写成21个连续素数的总和,但我找不到它.

Answer 1

你的代码是正确的.我运行它并确实产生了数字953,所以问题可能在于你的主要生成函数.应该有78498个素数低于一百万 - 你可能想检查你是否得到了这个结果.

也就是说,你的代码需要很长时间才能运行,因为它会调用check()3,080,928,753次.您可能想要找到一种检查较少总和的方法.我不会扩展这个,因为你没有要求破坏者,但如果你对一般提示感兴趣,请告诉我.