简要题解如下：
区间修改问题，使用差分转化为单点问题。
问题变成，一开始有 \(2n\) 个点为 \(1\)，每次操作可以选择 \(r - l\) 为奇质数的两个点 \(l, r\) 使其
^\(1\)。根据哥德巴赫猜想可以发现，若 \(r - l\) 为奇质数显然一次即可，若 \(r - l\) 为偶数则需两次，若 \(r - l\) 为奇数则需三次。
近一步可以发现，若想消去两个点 \(l, r\) 则涉及其他点是可以通过调整使得直接消去两个点的。
更近一步可以发现，将所有点按照奇偶分类，显然若消去奇偶性相同的两个数只能 \(2\) 次，那么首先将差是奇质数的点一起消去肯定是最优的。
因为差是奇质数的点必然一个为偶数一个为奇数构成二分图，于是可以使用匈牙利或网络流解决二分图最大匹配问题。
剩下的肯定要同集合内部按照 \(2\) 次消去，最后若还剩一个元素才使用 \(3\) 次的方法。
#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
#define Next(i, u) for (int i = cur[u]; i; i = e[i].next)
const int N = 2e4 + 5;
const int M = 1e7 + 5;
struct edge { int v, next, w;} e[N << 1];
int n, s, t, F, ans, cnt, tot = 1, ton[2], a[N], h[N], d[M];
namespace PR {
bool iprime[M]; int tot, prime[M];
void sieve(int L) {
iprime[1] = 1;
rep(i, 2, L) {
if(!iprime[i]) prime[++tot] = i;
for (int j = 1; j <= tot && i * prime[j] <= L; ++j) {
iprime[i * prime[j]] = true;
if(i % prime[j] == 0) break;
}
}
}
}
namespace FL {
bool book[N]; int dep[N], cur[N];
bool bfs(int s, int t) {
rep(i, s, t) cur[i] = h[i], dep[i] = -t;
queue <int> Q;
dep[s] = 1, Q.push(s);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
Next(i, u) {
int v = e[i].v; if(!e[i].w || dep[v] > 0) continue;
dep[v] = dep[u] + 1, Q.push(v);
}
}
return dep[t] > 0;
}
int dfs(int u, int lim) {
if(u == t) return lim;
int flow = 0, rflow = 0; book[u] = true;
Next(i, u) {
int v = e[i].v; cur[u] = i;
if(!book[v] && dep[v] == dep[u] + 1 && e[i].w && (rflow = dfs(v, min(e[i].w, lim)))) {
flow += rflow, lim -= rflow, e[i].w -= rflow, e[i ^ 1].w += rflow;
if(!lim) break;
}
}
book[u] = false; return flow;
}
}
void add(int u, int v, int w) {
e[++tot].v = v, e[tot].w = w, e[tot].next = h[u], h[u] = tot;
e[++tot].v = u, e[tot].w = 0, e[tot].next = h[v], h[v] = tot;
}
int main () {
cin >> n;
rep(i, 1, n) cin >> a[i], d[a[i]] ^= 1, d[a[i] + 1] ^= 1;
PR :: sieve(M - 1);
s = cnt = 1;
rep(i, 1, M - 1) if(d[i]) a[++cnt] = i, ++ton[i & 1];
t = ++cnt;
rep(i, 2, cnt - 1) {
if(a[i] & 1) add(s, i, 1);
else add(i, t, 1);
}
rep(i, 2, cnt - 1) if(a[i] & 1) {
rep(j, 2, cnt - 1) if(!(a[j] & 1) && !(PR :: iprime[abs(a[j] - a[i])])) add(i, j, 1);
}
while (FL :: bfs(s, t)) ans += FL :: dfs(s, cnt);
if((ton[0] - ans) & 1) F = 1;
ans += 2 * ((ton[0] - ans) / 2 + (ton[1] - ans) / 2);
ans += F * 3;
printf("%d", ans);
return 0;
}
首先区间修改差分转单点是非常重要的，可以减少有效修改点数，方便于观察问题。
对于某个数能被质数 / 奇质数组成的问题，一定要敏锐地想到 哥德巴赫猜想