#include <bits/stdc++.h>
#define yabs(x) ((x<0)?(-(x)):(x))

const int N=1e7+5,Node=210;

struct Edge{ int to,next; }way[Node*Node];
int n,x[Node],prime[N],cntprime,tot,num[Node],put[Node];
bool v[N],notprime[N],use[Node];

void Build(int a,int b) { way[++tot]=(Edge){b,num[a]}; num[a]=tot; }

void AddEdge(int a,int b) { Build(a,b); Build(b,a); }

void Init() {
	scanf("%d",&n);
	int x;
	for (int i=1;i<=n;++i) scanf("%d",&x),v[x]=1;
}

void Euler() {
	notprime[1]=1;
	for (int i=2;i<=10000000;++i) {
		if (!notprime[i]) prime[++cntprime]=i;
		for (int j=1;j<=cntprime && 1ll*i*prime[j]<=10000000;++j) {
			notprime[i*prime[j]]=1;
			if (!(i%prime[j])) break;
		}
	}
}

bool Dfs(int x) {
	for (int i=num[x];i;i=way[i].next) {
		int v=way[i].to;
		if (!use[v]) {
			use[v]=1;
			if (put[v]==-1 || Dfs(put[v])) {
				put[v]=x;
				return 1;
			}
		}
	}
	return 0;
}

void Solve() {
	Euler();
	int top=0,cnt1=0,cnt0=0;
	v[0]=0;
	for (int i=1;i<=10000001;++i) {
		bool fl=(v[i]!=v[i-1]);
		if (fl) x[++top]=i,cnt1+=i&1;
	}
	cnt0=top-cnt1;
	for (int i=1;i<=top;++i) if (x[i]&1) {
		for (int j=1;j<=top;++j) if (!(x[j]&1)) {
			if (!notprime[yabs(x[j]-x[i])]) {
				AddEdge(i,j);
			}
		}
	}
	int ans=0;
	for (int i=1;i<=top;++i) put[i]=-1;
	for (int i=1;i<=top;++i) if (x[i]&1) {
		memset(use,0,sizeof(use));
		if (Dfs(i)) ans++;
	}
	printf("%d\n",ans+(cnt0-ans)/2*2+(cnt1-ans)/2*2+(cnt0-ans)%2*3);
}

int main() {
	Init();
	Solve();
	return 0;
}