#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a;i<=b;++i)
typedef long long ll;

using namespace std;

void File(){
	freopen("ARC80F.in","r",stdin);
	freopen("ARC80F.out","w",stdout);
}

const int maxn=500+10;
int n,a[maxn],pos[maxn],tot,cnt,ans;
int be[maxn],cnte,to[maxn*maxn],las[maxn*maxn],beg[maxn];
bool vis[maxn];

void add(int u,int v){
	las[++cnte]=beg[u];
	beg[u]=cnte;
	to[cnte]=v;
}

bool pd(int x){
	if(x==1 || x==2)return false;
	int y=sqrt(x);
	REP(i,2,y)if(x%i==0)return false;
	return true;
}

bool Hungary(int u){
	for(int i=beg[u];i;i=las[i]){
		if(vis[to[i]])continue;
		vis[to[i]]=1;
		if(!be[to[i]] || Hungary(be[to[i]])){
			be[to[i]]=u;
			return true;
		}
	}
	return false;
}

int main(){
	//File();
	scanf("%d",&n);
	REP(i,1,n){
		scanf("%d",&a[i]);
		if(i==1 || a[i-1]<a[i]-1)pos[++tot]=a[i];
		if(i!=1 && a[i]>a[i-1]+1)pos[++tot]=a[i-1]+1;
	}
	pos[++tot]=a[n]+1;
	REP(i,1,tot)if(pos[i]%2)++cnt;
	REP(i,1,tot)if(pos[i]%2==0){
		REP(j,1,tot)if(pos[j]%2==1 && pd(abs(pos[j]-pos[i])))
			add(i,j);
	}
	REP(i,1,tot)if(pos[i]%2==0){
		memset(vis,0,sizeof(vis));
		ans+=Hungary(i);
	}
	printf("%d\n",ans+(tot-ans*2)+(cnt-ans)%2);
	return 0;
}
