0060 素数对集
* * * *
拉格朗日计划
* * * *
素数对集

取素数集合$\{3,7,109,673\}$中的任意两个数首尾相连,所得的12个数都是素数。例如选择7和109,连接后得到7109和1097都是素数。

该素数集合中的元素之和是$3+7+109+673=792$,是具备这一性质的四元素数集中最小的和数。

具备这一性质的五元素数集中最小的和数是多少?

本题难度:



解答

先尝试和猜测一个合理的上界,比如五个素数都在$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])