050. 连续素数的和(consecutive prime sum)

素数41可以写成六个连续素数的和:

$$ 41 = 2 + 3 + 5 + 7 + 11 + 13 $$
这是一百以下可以被写成连续素数的和中包含素数最多的。一千以下可以被写成连续素数的和,并且包含素数最多的素数是953,这个和中包含21个素数。求一百万以下可以被写成包含最多的连续素数的和的素数。

分析:先考虑最简单的情况,如何求出一个一百以下的素数,它可以表示为连续素数的和并且这个和包含最多的素数?题目已经给出了这个数是四十一,可以表示为从二至十三的连续素数的和,包含的素数个数为六个。看到这个问题,我们首先可以想到从二开始不断累加素数,加到这个和刚好超过一百为止,这时候得到素数序列为二到二十三的素数,我们截去最后一个素数,得到的素数序列即为其总和不超过一百的最长素数序列,也即[2, 3, 5, 7, 11, 13, 17, 19]。这个序列包含的素数有八个,其总和为77,显然不是素数。然后我们分析七个连续素数的情况,这只能包含两个序列,即[2, 3, 5, 7, 11, 13, 17]和[3, 5, 7, 11, 13, 17, 19],两个列表的和也不是素数,仍然排除。然后我们观察六个连续素数,则有[2, 3, 5, 7, 11, 13]、[3, 5, 7, 11, 13, 17]和[5, 7, 11, 13, 17, 19]三种情况,对应的和值分别为41, 56和72,显然只有41是素数,则我们可以得出结论41是一百以下可以表示为连续素数的和并且这个和包含最多的素数的素数,包含的素数个数为六个。

对于一百万以下的素数,我们也可以采用类似的思路,即首先产生一个从二开始的连续素数列表,其总和应该刚好要超过一百万。然后我们使用两个循环,外循环确定素数个数,从列表的长度减一逐渐递减到零;内循环确定连续素数的起始素数,从列表中第一个元素也就是二开始逐渐递增。然后观察这个新列表的和是否为一个素数,如果得到了一个素数,则可以直接返回结果,即为题目所求;如果没有,则继续循环,只到找到一个满足要求的素数。需要注意的是,我们额外编写了一个函数确定合理的素数上界是多少,通过单独编写函数将这一部分逻辑分离出来,可以使得主函数的结构更加清晰,这一部分逻辑也可以更好的复用。

from sympy import isprime,primerange,nextprime

def primesum_below_N(N):
    start = 2
    arr = [start]
    while True:
        nextp = nextprime(start)
        arr.append(nextp)
        if sum(arr)>=N:
            return arr[:-1]
        start = nextp

def main(N=10**6):
    primes = primesum_below_N(N)
    length = len(primes)
    for d in range(length-1,0,-1):
        for start in range((length-d+1)):
            res = sum(primes[start:start+d])
            if isprime(res):
                return res