忽略编号小于 $7$ 的结点（将求得的答案加上 $6$ 即可），设不大于 $n$ 的最大质数为 $p$：

• 对于编号大于 $p$ 的结点，向 $p$ 号结点连边最优。
• 对与编号小于 $p$ 的非质数结点，将它们连向最近的质数结点最优。
• 对于质数结点，将它们从小到大连成一条链最优，此时相邻两个质数间可以免费串联一个非直属结点 —— 将相邻两个质数的平均数串联上去最优。

用欧拉筛筛出不大于 $n$ 的所有质数后根据上述结论直接计算即可，过程中需要结合双指针快速找出最近的质数。

最终的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 12, M = 6e6 + 12;
int pp = 0, ps[M];
bitset <N> pt;
int main()
{
	freopen("tsp.in", "r", stdin);
	freopen("tsp.out", "w", stdout);
	int n, pp = 0, ans = 6, pi = 4;
	cin >> n;
	if (n <= 8)
	{
		cout << n - 1 << endl;
		return 0;
	}
	for (int i = 2; i <= n; i++)
	{
		if (!pt[i])
		{
			pp++;
			ps[pp] = i;
		}
		for (int j = 1; j <= pp; j++)
		{
			int h = ps[j] * i;
			if (h > n) break;
			pt[h] = true;
			if (i % ps[j] == 0) break;
		}
	}
	ps[pp + 1] = 2 * N;
	for (int i = 8; i <= n; i++)
	{
		if (pi < pp && ps[pi + 1] == i)
		{
			ans += ps[pi + 1] - ps[pi];
			pi++;
			continue;
		}
		if (ps[pi + 1] - i == i - ps[pi]) continue;
		ans += min(ps[pi + 1] - i, i - ps[pi]);
	}
	cout << ans << endl;
	return 0;
}