我们注意到有ai>1，所以，ai+aj为质数当且仅当两者奇偶性不同
我们可以以此将这个图变成一个二分图跑匈牙利算法即可
（这个题n只有40害得我想了半天状压dp和折半搜索，坑。。。）
#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 100
using namespace std;
vector<int> s[N]; bool vis[100];
int ans=0,n,f[100],v[100],pr[3000];
bool match(int x){
for(int i=0;i<s[x].size();++i)
if(!vis[s[x][i]]){ vis[s[x][i]]=1;
if(!f[s[x][i]] || match(f[s[x][i]])){ f[s[x][i]]=x; return 1; }
}
return 0;
}
int main(){
freopen("prime.in","r",stdin);
freopen("prime.out","w",stdout);
for(int i=2;i<=3000;++i)
if(!pr[i]) for(int j=i+i;j<=3000;j+=i) pr[j]=1;
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",v+i);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(!pr[v[i]+v[j]]) s[i].push_back(j);
for(int i=1;i<=n;++i){
memset(vis,0,sizeof vis);
if((v[i]&1)&&match(i)) ans++;
} printf("%d
",ans);
}