0050 连续素数之和
* * * *
拉格朗日计划
* * * *
连续素数之和

素数41可以写成六个连续素数之和:$41=2+3+5+7+11+13$。

在小于100的素数中,41是能写成最多个连续素数之和的数。

在小于1000的素数中,953是能被写成最多个连续素数之和的数,它能写成21个连续素数之和。

在小于一百万的素数中,哪个素数能够被写成最多的连续素数的和?

本题难度:



解答

先用筛法找出一百万以内的所有素数,再分别计算以每个数为起点时的最长序列。

由题面的信息知这样的序列中最少有21项,而第4900至第4920个素数之和恰超过一百万,因此只需考虑以前4900个素数为起点的情况即可。

结果是$997651$,它是从7开始的连续543个素数之和。

target=1000000
d=[0]*target
n=2

while n < target:
    for i in range(n+n,target,n):
        d[i]=d[i]+1
    n=n+1
    while n < target and d[n]>0:
        n=n+1

primeList=[k for k in range(2,target) if d[k]==0]
primeSet=set(primeList)

m=1
rs=ri=rm=-1
for i in range(4900):
    s=primeList[i]+primeList[i+1]
    j=i+2
    while s < target:
        if s in primeSet:
            if j-i>m:
                m=j-i
                rs=s
                ri=i
                rm=m
        s+=primeList[j]
        j+=1

print rs,primeList[ri],rm