5

我正在研究 Project Euler Problem 50，其中指出：

素数 41 可以写成六个连续素数之和：

41 = 2 + 3 + 5 + 7 + 11 + 13 这是添加到小于 100 的素数的最长连续素数之和。

加到一个素数上的小于一千的连续素数的最长和包含 21 项，等于 953。

100 万以下的哪个素数可以写成最连续素数之和？

为了确定素数P中的项（如果它可以写成素数之和），我使用所有素数（按递增顺序）直到（但不包括）P的滑动窗口，并计算所有素数的总和这些窗口，如果总和等于所考虑的素数，我计算窗口的长度......

这适用于所有最高1000的素数，但对于最高10**6的素数，它非常慢，所以我希望memozation会有所帮助；在计算滑动窗口的总和时，做了很多双重工作......（对吧？）

所以我在网上找到了标准的 memoizaton 实现并将其粘贴到我的代码中，这是正确的吗？（我不知道它应该如何在这里工作......）

primes = tuple(n for n in range(1, 10**6) if is_prime(n)==True)

count_best = 0


##http://docs.python.org/release/2.3.5/lib/itertools-example.html:
## Slightly modified (first for loop)
from itertools import islice
    def window(seq):
    for n in range(2, len(seq) + 1):

        it = iter(seq)
        result = tuple(islice(it, n))
        if len(result) == n:
            yield result    
        for elem in it:
            result = result[1:] + (elem,)
            yield result   

def memoize(function):
    cache = {}
    def decorated_function(*args):
        if args in cache:
            return cache[args]
        else:
            val = function(*args)
            cache[args] = val
            return val
    return decorated_function


@memoize 


def find_lin_comb(prime):
    global count_best

    for windows in window(primes[0 : primes.index(prime)]):
        if sum(windows) == prime and len(windows) > count_best:
            count_best = len(windows)
            print('Prime: ', prime, 'Terms: ', count_best)


##Find them:
for x in primes[::-1]: find_lin_comb(x)

（顺便说一句，素数的元组是“体面地”快速生成的）

感谢所有输入，我只是一个业余程序员，所以请不要对我进阶。

谢谢！

编辑：这是一个没有破坏缩进的工作代码粘贴：http: //pastebin.com/R1NpMqgb

4

2 回答 2

3

这适用于所有最高 1000 的素数，但对于最高 10**6 的素数，它非常慢，所以我希望 memozation 会有所帮助；在计算滑动窗口的总和时，做了很多双重工作......（对吧？）

是的，没错。当然，对于高达 10 6的素数来说，它的速度很慢。

假设您有n到 的素数N，按升序编号，p_1 = 2, p_2 = 3, ...。在考虑是否素数时。k是连续素数之和，您考虑所有窗口[p_i, ..., p_j]，对于(i,j)与i < j < k. 有(k-1)*(k-2)/2他们。通过所有k到n，您n³/6总共检查窗口（计算多重性，您正在检查w(i.j)总n-j次数）。即使忽略创建窗口并对其求和的成本，您也可以看到它是如何严重扩展的：

  • 对于N = 1000，有n = 168质数和大约 790000 个窗口要检查（计算多重性）。
  • 对于N = 10**6，n = 78498有素数和关于8.3*10**13窗口要检查。

现在将创建和求和窗口的工作考虑在内，估计对 中的素数j-i+1求和的工作量较低，工作量约为，总工作量大致变为。大概是 3300 万步，花生，但几乎是.j-i+1w(i,j)p_kk³/6k**4/24N = 10001.6*10**18N = 1000000

一年包含大约3.1*10**7几秒钟，使用 ~3GHz CPU，大约是 10 17 个时钟周期。所以我们说的操作需要大约 100 个 CPU 年（可能是 10 倍左右）。

我想你不愿意等那么久；）

现在，通过记忆，您仍然可以多次查看每个窗口，但您只对每个窗口进行一次计算。这意味着您需要n³/6计算窗口的工作量，并查看n³/6任何窗口的时间。

  • 问题1：您仍然需要查看窗口大约8.3*10**13几次，即使查看仅花费一个周期也需要几个小时。
  • 问题2：有关于记忆的8.3*10**13窗口。你没有那么多内存，除非你可以使用一个非常大的高清。

您可以通过丢弃不再需要的数据并仅在需要时为窗口计算数据来规避内存问题，但是一旦您知道何时可以丢弃哪些数据，您应该能够看到更好的方法.

加到一个素数上的小于一千的连续素数的最长和包含 21 项，等于 953。

这告诉您关于生成该总和的窗口的什么信息？它可以从哪里开始，又可以在哪里停止？您如何使用这些信息来创建有效的算法来解决问题？

于 2012-05-22T14:18:35.850 回答
1

memoize 装饰器向函数添加一个包装器，以缓存参数的每个值的返回值（在多个参数的情况下，每个值组合）。当使用相同的参数多次调用函数时，它很有用。您只能将其与纯函数一起使用，即

  1. 该功能没有副作用。更改全局变量并进行输出是副作用的示例。
  2. 返回值仅取决于参数的值，而不取决于某些可能在调用之间更改值的全局变量。

您的 find_lin_comb 函数不满足上述条件。一方面，它每次都使用不同的参数调用，另一方面，该函数不返回值。

于 2012-05-20T19:49:55.547 回答