先尝试和猜测一个合理的上界,比如五个素数都在$10000$以下。用筛法生成这一范围内的所有素数。
对每个素数p,维护一个能与之配对的素数列表d[p]。
遍历素数表,对素数p,从d[p]中取出q,再从d[p]和d[q]的交集中取出r,再从d[p]、d[q]、d[r]的交集中取出s,若d[p],d[q],d[r],d[s]的交集非空,则其中的元素都可以作为第五个元素t。
在所有可能的组合取出和最小的即可,结果是$26033$,对应的素数集是$\{13,5197,5701,6733,8389\}$。
target=10000
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)
n=len(primeList)
def isPrime(m):
if m <=target:
return m in primeSet
else:
i=0
while i < n and primeList[i]*primeList[i] <=m and m%primeList[i]:
i+=1
return i>=n or m%primeList[i]>0
d={}
for p in primeList:
d[p]=set([])
for i in range(n-1):
for j in range(i+1,n):
if isPrime(int(str(primeList[i])+str(primeList[j]))) and isPrime(int(str(primeList[j])+str(primeList[i]))):
d[primeList[i]].add(primeList[j])
print min([p+q+r+s+t,p,q,r,s,t] for p in primeList for q in d[p] for r in d[q] & d[p] for s in d[r] & d[q] & d[p] for t in d[s] & d[r] & d[q] & d[p])
|