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

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

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

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