#include<bits/stdc++.h>
using namespace std;
#define RI register int
#define LL long long
inline int read()
{
	int res=0,f=1;
	char ch=getchar();
	while(ch!='-'&&(ch>'9'||ch<'0'))
		ch=getchar();
	if(ch=='-')
		f=-1,ch=getchar();
	while(ch>='0'&&ch<='9')
		res=(res<<1)+(res<<3)+(ch^48),ch=getchar();
	return res*f;
}
int k,a[1005];
namespace subtask1
{
	int f[1050000];
	//f[i]表示状态为i时到达最终状态的最少操作数
	bool v[25],prime[25];
	queue<int> q;
	vector<int> s[20];
	//s[i]表示左端点为i时合法的右端点
	void bfs()
	{
		memset(f,0x3f,sizeof(f));
		q.push((1<<20)-1);
		f[(1<<20)-1]=0;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(RI i=1;i<=18;++i)
			{
				int size=s[i].size();
				for(RI j=0;j<size;++j)
				{
					int l=i,r=s[i][j];
					int t=0;
					for(RI g=l;g<=r;++g)
						t+=1<<(g-1);
					if(f[x^t]>f[x]+1)
					{
						f[x^t]=f[x]+1;
						q.push(x^t);
					}
				}
			}
		}
		return;
	}
	int main()
	{
		prime[3]=prime[5]=prime[7]=prime[11]=prime[13]=prime[17]=prime[19]=1;
		for(RI t=3;t<=20;++t)
		{
			if(!prime[t])
				continue;
			for(RI i=1;i<=20;++i)
			{
				if(i+t-1>20)
					break;
				s[i].push_back(i+t-1);
			}
		}
		bfs();
		int t=0;
		for(RI i=1;i<=k;++i)
			v[a[i]]=1;
		for(RI i=1;i<=20;++i)
			if(!v[i])
				t+=1<<(i-1);
		printf("%d\n",f[t]);
		return 0;
	}
}
namespace final
{
	int maxn;
	struct edge{
		int nxt,to,w;
	}e[1000005];
	int h[10000005],tot,d[10000005],b[10000005];
	void add(int x,int y,int w)
	{
		e[++tot].nxt=h[x];
		e[tot].to=y;
		e[tot].w=w;
		h[x]=tot;
	}
	int prime[664600],v[10000005],cnt;
	void pre(int x)
	{
		for(RI i=2;i<=x;i++)
		{
			if(!v[i])
			{
				prime[++cnt]=i;
				v[i]=i;
			}
			for(RI j=1;j<=cnt;++j)
			{
				if(prime[j]*i>x||prime[j]>v[i])
					break;
				v[prime[j]*i]=prime[j];
			}
		}
		v[2]=0;
	}
	queue<int> q;
	bool bfs()
	{
		while(q.size())
			q.pop();
		memset(d,0,sizeof(d));
		q.push(0);
		d[0]=1;
		while(!q.empty())
		{
			int x=q.front();
			q.pop();
			if(x==maxn+2)
				break;
			for(RI i=h[x];i;i=e[i].nxt)
			{
				int y=e[i].to;
				if(!e[i].w)
					continue;
				if(d[y])
					continue;
				d[y]=d[x]+1;
				q.push(y);
			}
		}
		return d[maxn+2];
	}
	int dinic(int x,int flow)
	{
		if(x==maxn+2)
			return flow;
		int rest=flow,t;
		for(RI i=h[x];i;i=e[i].nxt)
		{
			if(!rest)
				break;
			int y=e[i].to;
			if(d[y]!=d[x]+1||!e[i].w)
				continue;
			t=dinic(y,min(rest,e[i].w));
			rest-=t,e[i].w-=t,e[i^1].w+=t;
		}
		return flow-rest;
	}
	int l[5000005],r[5000005];
	//l表示下标为奇数的点
	//r表示下标为偶数的点
	int main()
	{
		for(RI i=1;i<=k;++i)
		{
			b[a[i]]=1;
			maxn=max(maxn,a[i]);
		}
		pre(maxn+2);
		for(RI i=1;i<=maxn+1;++i)
			if(b[i]!=b[i-1])
			{
				if(i&1)
					l[++l[0]]=i;
				else
					r[++r[0]]=i;
			}
		tot=1;
		for(RI i=1;i<=l[0];++i)
			for(RI j=1;j<=r[0];++j)
				if(abs(l[i]-r[j])==v[abs(l[i]-r[j])])
					add(l[i],r[j],1),add(r[j],l[i],0);
		for(RI i=1;i<=l[0];++i)
			add(0,l[i],1),add(l[i],0,0);
		for(RI i=1;i<=r[0];++i)
			add(r[i],maxn+2,1),add(maxn+2,r[i],0);
		int flow,ans=0;
		while(bfs())
			while(flow=dinic(0,1<<30))
				ans+=flow;
		l[0]-=ans,r[0]-=ans;
		ans+=l[0]/2*2,ans+=r[0]/2*2;
		if(l[0]&1)
			ans+=3;
		printf("%d\n",ans);
		return 0;
	}
}
int main()
{
	//freopen("oatmeal.in","r",stdin);
	//freopen("oatmeal.out","w",stdout);
	k=read();
	bool flag=1;
	for(RI i=1;i<=k;++i)
	{
		a[i]=read();
		if(a[i]>20)
			flag=0;
	}
	//if(flag)
	//	return subtask1::main();
	return final::main();
}


Measured memory_bytes: 164096