我正在解决欧拉计划(Project Euler)第50个问题,它陈述如下:
质数41可以表示为6个连续质数之和: 41 = 2 + 3 + 5 + 7 + 11 + 13 这是在小于100的质数中,加起来是质数且连续的质数之和最长的。
小于1000的质数中,加起来是质数且连续的质数之和最长的包含21个质数的和,并等于953。
在小于一百万的质数中,哪个质数能够被表示成连续质数之和的形式,而且能表示出的连续质数个数最多?
为了确定质数P是否可以表示为质数之和,我使用从第一个质数开始到(但不包括)P的所有质数的滑动窗口,计算所有这些窗口的总和,如果总和等于所考虑的质数,则计算窗口长度...
这对于小于1000的所有质数都很好用,但对于小于10 ** 6的质数来说速度非常慢,因此我希望使用“记忆化(memozation)”,当计算滑动窗口的总和时,会有很多重复的工作...(对吗?)
因此,我在网上找到了标准的记忆化实现方法,只是把它粘贴到我的代码中,这样做正确吗?(我不知道它在这里应该如何工作...)
(顺便提一句,质数元组生成速度相当快)
欢迎提供任何输入。我只是一个业余程序员,请不要对我过于深奥。
谢谢!
编辑:这里有一个可用的代码片段,没有破坏缩进: http://pastebin.com/R1NpMqgb
质数41可以表示为6个连续质数之和: 41 = 2 + 3 + 5 + 7 + 11 + 13 这是在小于100的质数中,加起来是质数且连续的质数之和最长的。
小于1000的质数中,加起来是质数且连续的质数之和最长的包含21个质数的和,并等于953。
在小于一百万的质数中,哪个质数能够被表示成连续质数之和的形式,而且能表示出的连续质数个数最多?
为了确定质数P是否可以表示为质数之和,我使用从第一个质数开始到(但不包括)P的所有质数的滑动窗口,计算所有这些窗口的总和,如果总和等于所考虑的质数,则计算窗口长度...
这对于小于1000的所有质数都很好用,但对于小于10 ** 6的质数来说速度非常慢,因此我希望使用“记忆化(memozation)”,当计算滑动窗口的总和时,会有很多重复的工作...(对吗?)
因此,我在网上找到了标准的记忆化实现方法,只是把它粘贴到我的代码中,这样做正确吗?(我不知道它在这里应该如何工作...)
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