显然每个素数p只能作为素因子在该子集中出现至多一次，其出现形式有这样三种情况：
（1）若p特别大，即$2p>n$，那么它只能以单个素数p的形式出现。
（2）以素幂$p^k$的形式出现，其中$k>1$，显然这只有在$p^2 < n$时才有可能。
（3）以$dp^a$的形式出现，其中$d>1$，这就要求$2p\le n$。此外，若q是d的素因子，那么q就不能再作为该子集中其他数的素因子。
这使得本题转换为最小费用最大流问题，即先假设所有的素数都以（1）（2）的形态出现，再考察能否将一些（2）的情况转换为（3），也就是比较$p\cdot f(p,n/d)$和$f(p,n)+d$，其中$f(p,m)$表示p的不超过m的最大幂。
具体实现使用networkx库中提供的函数，最终结果是$1726545007$。
注：因需调用networkx库，以下代码为Python 3。
import networkx
target=200000
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]
def f(p,bound=target):
q=1
while q <= bound:
q*=p
return q//p
g=networkx.DiGraph()
a,b=[],[]
for p in primeList:
if p*p <= target:
g.add_edge(-1,p,capacity=1,weight=0)
a.append(p)
elif p+p <= target:
g.add_edge(p,-2,capacity=1,weight=0)
b.append(p)
else:
break
for p in a:
for q in b:
if p*q>target:
break
if f(p)+q < (k:=f(p,target//q)*q):
g.add_edge(p,q,capacity=1,weight=-k+f(p)+q)
print(1+sum(map(f,primeList))-networkx.cost_of_flow(g,networkx.max_flow_min_cost(g,-1,-2)))
|
