#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=2e7+10;
bool vis[maxn];
ll prime[maxn/10], p_sz, z;
void get_number() {
	for(int i=2;i<maxn;i++){
		if (!vis[i]) {
			prime[p_sz++] = i;
		}
		for(ll j=0;j<p_sz&&(z=i*prime[j])<maxn;++j) {
			vis[z] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
const int p_max=810,q_max=1000010;
int n,m,s,t,edge=1;
int d[p_max],now[p_max],to[q_max],Next[q_max],fir[q_max];
int v[q_max],ans=0;
void add(int x,int y,int w){
	to[++edge]=y; v[edge]=w; Next[edge]=fir[x]; fir[x]=edge;
	to[++edge]=x; v[edge]=0; Next[edge]=fir[y]; fir[y]=edge;
}
bool bfs(){
	memset(d,0, sizeof(d));
	queue<int> q;
	q.push(s);
	d[s]=1;
	now[s]=fir[s];
	while(!q.empty()){
		int x=q.front();q.pop();
		for(int i=fir[x];i;i=Next[i]){
			if(!d[to[i]]&&v[i]){//为分层且有权值的边才进行遍历
				q.push(to[i]);
				now[to[i]]=fir[to[i]];
				d[to[i]]=d[x]+1;
				if(to[i]==t) return true;
			}
		}
	}
	return false;
}
int dfs(int u, int flow){
	if(u==t) return flow;
	int rest=flow,k,i;
	for(i=now[u];i&&rest;i=Next[i]){
		if(v[i]&&d[to[i]]==d[u]+1){
			k=dfs(to[i],min(rest,v[i]));//找最小流
			if(!k) d[to[i]]=0;//剪枝，删掉已经增广过的点
			v[i]-=k;
			v[i^1]+=k;
			rest-=k;//从u出发的点要消耗k
		}
	}
	now[u]=i;//将u的下一个结点置空，避免重复
	return flow-rest;//返回在u点的最大流出
}
int dinic(){
	ans=0;
	while(bfs()) ans+=dfs(s,1e8);
	return ans;
}
int main(){
	get_number();
	cin>>n;
	vector<int> p(n+1);
	int flag=1,cnt=0;
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(x==1){
			if(flag==0) continue;
			flag=0;
		}
		p[++cnt]=x;
	}
	n=cnt,s=0,t=n+1;
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(!vis[p[i]+p[j]])add(i,j,1);
	for(int i=1;i<=n;i++){
		if(p[i]%2) add(s,i,1);
		else add(i,t,1);
	}
	cout<<n-dinic()<<endl;
	return 0;
}