\(n^3\) 匈牙利最优解，根本叉不掉。
分析
观察序列，如果把两个和为质数的点连一条边，那么原问题就转化成了求最大独立集。
有一种直觉告诉我们这应该是一个二分图，就考虑证明一下。
首先，偶数个 \(1\) 就违背了这一点，但当去掉重复的 \(1\) 后，它就是一个二分图。
不妨反证，设有一个由 \(x,y,z(x\le y\le z,1<y\le z)\) 构成的奇环，则：
\[\begin{cases}
x+y\equiv 1 \pmod 2\\
y+z\equiv 1 \pmod 2\\
x+z\equiv 1 \pmod 2
\end{cases}
\]
这是矛盾的，所以这个图是二分图。
在二分图上匈牙利求 \(n-\text{最大匹配数}\) 即可。
时间复杂度比较玄学，因为根本跑不满 \(n^3\)。
交一发结果发现 T 了一个点，考虑卡常。
卡常
优化枚举
首先可以把枚举所有的点 DFS 一遍改成只枚举某个部的点。在这道题中，数组元素的奇偶性天然分成了两个部，直接判断即可。
经过试验，偶数点较少一些，所以枚举偶数点。
优化建边
根据上述，只连偶数到奇数的单向边即可。
此外，还需要提高缓存命中。故排序时把偶数都放在前面，奇数放后面，也可以方便去掉重复的 \(1\)。
由于这是一个稠密图，vector 建边比链式前向星快不少。
优化匈牙利
DFS 常数巨大，改用 BFS 版，原理类似。
其他
比如位运算代替取模，多次定义改成赋值等等。都加上去就行。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3010,M=2e5+10;
int n,a[N],p[M],link[N],ans,fg[N],tim=1,q[N],hh,tt,px[N],py[N],pre[N];
bool vis[M],vx[N],vy[N];
vector<int>G[N];
inline bool cmp(int x,int y){
return ((x&1)^(y&1))?(~x&1):x>y;
}
inline void init(){
vis[1]=1;
for(int i=2;i<M;++i){
if(!vis[i]) p[++p[0]]=i;
for(int j=1;j<=p[0]&&1ll*i*p[j]<M;++j){
vis[i*p[j]]=1;
if(i%p[j]==0) break;
}
}
}
void aug(int v){
int t;
while(v){
t=px[pre[v]];
px[pre[v]]=v;
py[v]=pre[v];
v=t;
}
}
bool bfs(int s){
memset(pre,0,sizeof(pre));
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
q[hh=tt=1]=s;
int u;
while(hh<=tt){
u=q[hh++];
vx[u]=1;
for(int v:G[u]) if(!vy[v]){
vy[v]=1;
pre[v]=u;
if(!py[v]) return aug(v),1;
q[++tt]=py[v];
}
}
return 0;
}
int main(){
init();
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
sort(a+1,a+1+n,cmp);
while(n>1&&a[n-1]==1) --n;
for(int i=1;i<=n&&(~a[i]&1);++i){
for(int j=n;j>=1&&(a[j]&1);--j){
if(!vis[a[i]+a[j]]) G[i].emplace_back(j);
}
}
for(int i=1;i<=n&&(~a[i]&1);++i,++tim) ans+=bfs(i);
printf("%d",n-ans);
return 0;
}