頂点数を \(2\) 倍にすることで、最大流 \(1\) 回で解くことができます。

1. \(0\) から \(2N+1\) の番号がついた、 \(2N + 2\) 頂点のグラフを用意し、頂点 \(0\) を \(S\)、 頂点 \(2N+1\) を \(T\) とします。
2. 整数 \(i (1 \leq i \leq N)\) において、頂点 \(S\) から頂点 \(i\) と、頂点 \(i + N\) から頂点 \(T\) に容量 \(B_i\) の辺を追加します。
3. 整数 \(i, j (1 \leq i, j \leq N)\) において、\(A_i + A_j\) が素数ならば、 頂点 \(i\) から頂点 \(j + N\) に容量 \(\infty\) の辺を追加します。
4. 頂点 \(S\) から頂点 \(T\) への最大流を半分にしたものが答えです。

頂点数が \(O(N)\)、辺の数が \(O(N^2)\) であり、計算量 \(O(\sqrt{\text{max}(A_i)})\) の素数判定を \(N^2\) 回行うため、計算量は \(O(N^4 + N^2\sqrt{\text{max}(A_i)} )\) となります。

実装例(c++)