python - 我是否检查过该列表的每个连续子集？

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)

我想知道我是否对低于 100 万的两个或多个连续素数的总和调用了 check()

问题说有一个素数 953，可以写成 21 个连续素数的和，但我没有找到它。

Answer 1

您的代码是正确的。我运行了它，它确实生成了数字 953，所以问题可能出在你的素数生成函数上。应该有 78498 个低于 100 万的素数 - 您可能需要检查是否得到该结果。

也就是说，您的代码将需要很长时间才能运行，因为它将调用 check() 3,080,928,753 次。您可能想找到一种检查更少总和的方法。由于您不要求剧透，所以我不会对此进行详细说明，但如果您对一般提示感兴趣，请告诉我。