先用筛法找出不超过$10^7$的素数，从小到大依次遍历这些素数，对每个素数，生成不超过该数且与其相连的其他素数，用并查集标记和更新连接关系即可。
生成相连的其他素数时共有在最左侧添加一位，去掉最高位，以及替换一个数字三种情况，其中去掉最高位时还需注意排除次高位为0的情况（例如103不能直接去掉最高位变成3）。
以下代码中打印了进度信息，最终结果是$46479497324$。
target=10**7
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]
primeClass={p:p for p in primeList}
print("primes generated,start computing...")
tick=len(primeList)//100
def find(x):
if primeClass[x]==x:
return x
primeClass[x]=find(primeClass[x])
return primeClass[x]
def merge(x,y):
primeClass[find(x)]=find(y)
res=0
for k,p in enumerate(primeList):
s=str(p)
for q in [int(j+s) for j in "123456789"]+[int(s[:i]+j+s[i+1:]) for i in range(len(s)) for j in "0123456789"]:
if q < p and abs(len(str(q))-len(s)) < 2 and q in primeClass:
merge(p,q)
if find(p)!=find(2):
res+=p
if k%tick==0:
print k//tick,"completed, current sum:", res
print res
|
