2

我正在尝试解决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 个连续素数之和，但我没有找到它。

4

2 回答 2

5

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

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

于 2010-05-02T16:06:52.133 回答
0

我没有一个直接的答案，但是您是否尝试过将总和放入嵌套数组中，然后将素数 p 附加到子数组而不是将它们添加到求和计数器？这将让您直观地检查哪些素数被添加到每个子数组中，并且通过扩展会告诉您原始代码正在总结哪些素数。

于 2010-05-02T16:08:58.493 回答