先用筛法找出一百万以内的所有素数,再分别计算以每个数为起点时的最长序列。
由题面的信息知这样的序列中最少有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
|