#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 210
#define M N*N
#define MX 20000000
using namespace std;
int nxt[M<<1],to[M<<1],head[N],cnt;
bool vis[N<<1];
int link[N<<1],lf[N<<1],rf[N<<1],n,m;
int prime[MX],maxp[MX];
bool cant[MX];
void add(int u,int v)
{
	nxt[++cnt]=head[u];
	to[cnt]=v;
	head[u]=cnt;
}
bool check(int u)
{
	for(int i=head[u];i;i=nxt[i])
	{
		int v=to[i];
		if(vis[v]) continue;
		vis[v]=true;
		if(!link[v] || check(link[v]))
		{
			link[u]=v;
			link[v]=u;
			return true;
		}
	}
	return false;
}
void build()
{
	for(int i=1;i<=lf[0];i++)
	{
		int x=lf[i];
		for(int j=1;j<=rf[0];j++)
		{
			int y=rf[j];
			if(cant[abs(x-y)]) continue;
			add(i,j+lf[0]);
			add(j+lf[0],i);
		}
	}
}
bool color[MX];
int maxn=0;
void solve()
{
	lf[0]=rf[0]=0;
	for(int i=1;i<=maxn;i++)
		if(color[i]!=color[i-1])
		{
			if(i&1) rf[++rf[0]]=i;
			else lf[++lf[0]]=i;
		}
	build();
	int ans=0;
	for(int i=1;i<=lf[0];i++)
	if(!link[i])
	{
		memset(vis,0,sizeof(vis));
		ans+=check(i);
	}
	int res=0;
	if(ans<lf[0]) res+=(lf[0]-ans)/2*2;
	if(ans<rf[0]) res+=(rf[0]-ans)/2*2;
	if((lf[0]-ans)%2==1) res+=3;
	printf("%d\n",ans+res);
}
int main()
{
	int cnt=0;
	prime[1]=1;
	cant[1]=1;
	for(int i=2;i<=MX-10;++i)
	{
		if(!cant[i])
		{
			prime[++cnt]=i;
			maxp[i]=i;
		}
		for(int j=1;j<=cnt && i*prime[j]<=MX-10;j++)
		{
			cant[i*prime[j]]=true;
			if(i%prime[j]==0)
			{
				maxp[i*prime[j]]=prime[j];
				break;
			}
		}
	}
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int a;
		scanf("%d",&a);
		color[a]=true;
		maxn=max(maxn,a);
	}
	maxn++;
	solve();
	return 0;
}
