#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define rep(i,st,ed) for (int i=st;i<=ed;++i)

const int N=20005;
const int M=10000005;

std:: vector <int> vec[2];

struct edge {int x,y,next;} e[N*2];

int link[N],vis[N],a[M];
int ls[N],p[M/10],edCnt;

bool np[M];

int read() {
	int x=0,v=1; char ch=getchar();
	for (;ch<'0'||ch>'9';v=(ch=='-')?(-1):v,ch=getchar());
	for (;ch<='9'&&ch>='0';x=x*10+ch-'0',ch=getchar());
	return x*v;
}

void add_edge(int x,int y) {
	e[++edCnt]=(edge) {x,y,ls[x]}; ls[x]=edCnt;
	e[++edCnt]=(edge) {y,x,ls[y]}; ls[y]=edCnt;
}

void pre(int n) {
	np[1]=1;
	rep(i,2,n) {
		if (!np[i]) p[++p[0]]=i;
		for (int j=1;i*p[j]<=n;++j) {
			np[i*p[j]]=1;
			if (i%p[j]==0) break;
		}
	}
}

int find(int x,int id) {
	for (int i=ls[x];i;i=e[i].next) {
		if (vis[e[i].y]==id) continue;
		vis[e[i].y]=id;
		if (!link[e[i].y]||find(link[e[i].y],id)) {
			link[e[i].y]=x;
			return 1;
		}
	}
	return 0;
}

int main(void) {
	int n=read(),mx=0;
	rep(i,1,n) {
		int x=read();
		a[x]=1;
		mx=std:: max(mx,x);
	}
	pre(mx+1);
	rep(i,1,mx+1) if (a[i]!=a[i-1]) {
		vec[i&1].push_back(i);
	}
	int ta=vec[0].size(),tb=vec[1].size();
	for (int i=0;i<ta;++i) {
		for (int j=0;j<tb;++j) {
			int d=abs(vec[0][i]-vec[1][j]);
			if (!np[d]&&(d&1)) {
				add_edge(i+1,j+1+ta);
			}
		}
	}
	int ans=0;
	rep(i,1,ta) ans+=find(i,i);
	ta-=ans,tb-=ans;
	ans+=(ta/2)*2+(tb/2)*2;
	if ((ta&1)||(tb&1)) ans+=3;
	printf("%d\n", ans);
	return 0;
}