用筛法生成所有的真因数之和,逐个检查并缓存记录链长可得结果是$14316$,该链中有28项。
target=1000001
d=[1]*target
d[0]=d[1]=0
for n in range(2,target):
for i in range(n+n,target,n):
d[i]+=n
c=[0 if i>=target else -1 for i in d]
c[0]=c[1]=0
m=0
z=0
for n in range(2,target):
if c[n] < 0:
p=[]
j=n
while c[j] < 0 and j not in p:
p.append(j)
j=d[j]
if c[j]>=0:
for q in p:
c[q]=0
else:
k=p.index(j)
for q in p[:k]:
c[q]=0
for q in c[k:]:
c[q]=len(p)-k
if len(p)-k>m:
m=len(p)-k
z=min(p[k:])
elif len(p)-k==m:
z=min(p[k:]+[z])
print z
|