将所有正整数按如下方式排列成三角形的样式：

$\begin{matrix} 1 & & & & & & & & & & \\ \color{red}{2} & \color{red}{3} & & & & & & & & & \\ 4 & \color{red}{5} & 6 & & & & & & & & \\ \color{red}{7} & 8 & 9 & 10 & & & & & & & \\ \color{red}{11} & 12 & \color{red}{13} & 14 & 15 & & & & & & \\ 16 & \color{red}{17} & 18 & \color{red}{19} & 20 & 21 & & & & & \\ 22 & \color{red}{23} & 24 & 25 & 26 & 27 & 28 & & & & \\ \color{red}{29} & 30 & \color{red}{31} & 32 & 33 & 34 & 35 & 36 & & & \\ \color{red}{37} & 38 & 39 & 40 & \color{red}{41} & 42 & \color{red}{43} & 44 & 45 & & \\ 46 & \color{red}{47} & 48 & 49 & 50 & 51 & 52 & \color{red}{53} & 54 & 55 & \\ 56 & 57 & 58 & \color{red}{59} & 60 & \color{red}{61} & 62 & 63 & 64 & 65 & 66 \\ \ldots & & & & & & & & & & \end{matrix}$

在这个三角形中每个正整数最多有八个邻居。

若有三个素数中，其中两个均为另一个的邻居，那么称这三个素数称为一个素数三元组。

例如，第二行的素数2和3都是素数三元组$(2,3,5)$中的元素。

又如第八行的29和31都是素数三元组$(23,29,31)$中的元素。

但第九行只有37是素数三元组$(29,37,47)$中的元素，这一行中其它素数都不属于任何素数三元组。

记$S(n)$是第n行中属于素数三元组的所有素数之和，例如$S(8)=60$、$S(9)=37$。

可以验证$S(10000)=950007619$。

求$S(5678027)+S(7208785)$。

本题难度:

解答

非常繁琐而又意义不大的题。

要计算$S(n)$，需要考察第$n-2$、$n-1$、$n$、$n+1$、$n+2$共五行，这是因为若被考察的元素是i，那么i周围八个相邻位置的元素都有可能作为素数三元组的中心元素。

因此i在某个素数三元组中的条件是：i本身是素数，在其周围八个相邻位置的数中有某个数j是素数，且以j为中心的九宫格中至少有三个素数。

需要检验五行共5n个数的素性。第$n+2$行最后一个数是$(n+3)(n+2)/2$，先用筛法找出$\sqrt{(n+3)(n+2)/2}$以内的所有素数，用这些素数，再次使用筛法确定这5n个数的素性。

最后遍历第n行依次检验，结果是$322303240771079935$。

import math
a,b=5678027,7208785

target=int(math.sqrt((b+2)*(b+3)/2))+1
d=[0]*target
n=2
while n < target:
    for i in range(n*n,target,n):
        d[i]=d[i]+1
    n+=1
    while n < target and d[n]>0:
        n=n+1
primes=[k for k in range(2,target) if d[k]==0]

r=0
for x in [a,b]:
    m=(x+3)*(x+2)/2
    n=(x-3)*(x-2)/2
    d=[1]*(m-n)
    for p in primes:
        i=n+1
        if i%p>0:
            i=i+p-(i%p)
        if i==p:
            i=2*p
        while i <= m:
            d[i-n-1]=0
            i+=p
    s=sum(i for i in range(n+2*x,n+3*x-4) if d[i-n-1]==1 and any(d[[i-2*x+3,i-x+1,i,i+x,i+2*x+1][j]+k-n-1]==1 and sum(d[u+v-n-1] for u in [i-2*x+3,i-x+1,i,i+x,i+2*x+1][j-1:j+2] for v in [k-1,k,k+1])>=3 for j in [1,2,3] for k in [-1,0,1]))
    r+=s

print r