#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mx=1e7;
bool aa[mx+10],v[mx+10],mp[1010][1010];
int n,pr[2000010],a[1010],b[1010],bb[1010],c[1010],ans,mlby;
void ycl(){
	int i,j;
	for(i=2;i<=mx;i++){
		if(!v[i])pr[++pr[0]]=i;
		for(j=1;j<=pr[0]&&i*pr[j]<=mx;j++){
			v[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
	v[1]=v[2]=1;
}
int pd(int x){
	int i;
	if(bb[x])return 0;
	bb[x]=1;
	for(i=1;i<=b[0];i++)if(mp[x][i]&&(!c[i]||pd(c[i]))){
		c[i]=x;return 1;
	}
	return 0;
}
int main(){
	int i,x,j;
	ycl();
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		aa[x]=1;
	}
	for(i=1;i<=mx+1;i++)if(aa[i]!=aa[i-1]){
		if(i%2)a[++a[0]]=i;
		 else b[++b[0]]=i;
	}
	for(i=1;i<=a[0];i++)
	 for(j=1;j<=b[0];j++)if(!v[abs(a[i]-b[j])])mp[i][j]=1;
	for(i=1;i<=a[0];i++){
		for(j=1;j<=a[0];j++)bb[j]=0;
		if(pd(i))ans++;
	}
	mlby=ans+2*((a[0]-ans)/2+(b[0]-ans)/2);
	if((a[0]-ans)%2)mlby+=3;
	printf("%d",mlby);
}