頂点 \(1\) は必ず使うとして，以下ではそれを無視して考えます．

整数 \(x,y\) (\(x<y\)) に対し，頂点 \(x\) から \(y\) に行ける条件を考えます． 以下，整数 \(n\) に対して，\(n\) の最小の素因数を \(f(n)\) と表すことにします．

\(x,y\) の偶奇で場合分けすることで，以下のように条件をまとめることができます．

• \(x \equiv 0\), \(y \equiv 0\) のケース：必ず到達可能．
• \(x \equiv 1\), \(y \equiv 0\) のケース：\(x+f(x) \leq y\) と同値．
• \(x \equiv 0\), \(y \equiv 1\) のケース：\(x \leq y-f(y)\)と同値．
• \(x \equiv 1\), \(y \equiv 1\) のケース：\(x+f(x) \leq y-f(y)\)と同値．

\(x \equiv 0\), \(y \equiv 0\) のケースは自明なので，残りのケースについて説明します．

まず，\(x\) から遷移可能な最小の整数は \(x+f(x)\) です．ここで，\(x+f(x)\) は必ず偶数であることから， \(x \equiv 1\), \(y \equiv 0\) のケースについては上で示した条件が導かれます．

同様に，\(y\) へ遷移可能な最大の整数は \(y-f(y)\) であり，また \(y-f(y)\) が偶数であることから，\(x \equiv 0\), \(y \equiv 1\) のケースについても示されます．

最後のケースについて考えます．上の条件が十分であることは明らかなので，必要性を示します． 上の条件を満たさないが \(x \to y\) と遷移できる，というケースを考えます．\(2\) 回以上の遷移で \(x \to y\) と変化するならば，上の条件を満たすことになるので，\(x \to y\) と直接遷移するものだけ考えればよいです．\(x,y\) の共通の素因数を一つ取り，これを \(p\) とします．\(x=ap,y=bp\) と書くと，\(a,b\) は両方とも奇数になります． よって，\(x=ap<(a+1)p<bp=y\) であり，これは \(x \to y\) に \(2\) 回の遷移で至ることが可能であることを表します． よって，結局 \(x+f(x) \leq y-f(y)\) が満たされることになります． これで示されました．

整数 \(n\) に対して，\(l(n),r(n)\) を以下のように定義します．

• \(l(n)=n,r(n)=n+1\) (\(x \equiv 0 \mod 2\))
• \(l(n)=x-f(n)+1,r(n)=x+f(n)\) (\(x \equiv 1 \mod 2\))

すると，整数 \(x,y\) (\(x \neq y\)) に対して，\(x\) と \(y\) が互いに到達不能であることと，区間 \([l(x),r(x)), [l(y),r(y))\) が共通部分を持つことが同値になります．

元の問題に戻ります． 頂点集合を選んだ時，それらが問題文の条件を満たすなら，頂点に対応する区間すべてに含まれる点が存在することになります． よって結局，各 \(2 \leq i \leq N\) について，区間 \([l(i),r(i))\) に \(A_i\) を足す，という操作を行い，最後に全体の max を求めればよいことになります．

計算量は \(O(N)\) です．

解答例(c++)