#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
#include <cstring>
#include <set>
#include <cmath>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
const int MAX_N = 1e3 + 6;

struct CostFlow {
	static const int MAX_N = 1e3 + 6;
	struct Edge {
		int to,cap,rev,cost;
	};
	vector<Edge> edg[MAX_N];
	#define SZ(x) ((int)(x).size())
	void add_edge(int from,int to,int cap,int cost) {
		edg[from].push_back({to,cap,SZ(edg[to]),cost});
		edg[to].push_back({from,0,SZ(edg[from])-1,-cost});
	}
	int n,s,t;
	void init(int _n,int _s,int _t) {
		n=_n;
		s=_s;
		t=_t;
		for (int i=0;n>=i;i++) {
			edg[i].clear();
		}
	}
	static const int INF = 1e9 + 7;
	int dis[MAX_N];
	int pre[MAX_N],pre_id[MAX_N];
	bool in_que[MAX_N];
	pii flow() {
		int cost=0;
		int flow=0;
		while (true) {
//			cout<<"in"<<endl;
			for (int i=0;n>=i;i++) {
				dis[i] = INF;
				in_que[i]=0;
			}
			queue<int> que;
			que.push(s);
			dis[s] = 0;
			while (!que.empty()) {
				int t=que.front();
				que.pop();
				int id=0;
				in_que[t]=0;
				for (Edge e:edg[t]) {
					if (e.cap > 0 && dis[e.to] > dis[t] + e.cost) {
						dis[e.to] = dis[t] + e.cost;
						pre[e.to] = t;
						pre_id[e.to] = id;
						if (!in_que[e.to]) {
							in_que[e.to]=1;
							que.push(e.to);
						}
					}
					id++;
				}
			}
//			cout<<"haha"<<endl;
			if (dis[t] == INF || dis[t] == 3) break;
			int mn_flow = INF;
			for (int i=t;i!=s;i=pre[i]) {
//				cout<<"i = "<<i<<endl;
				mn_flow = min(mn_flow,edg[pre[i]][pre_id[i]].cap);
			}
//			cout<<"finish "<<endl;
			flow += mn_flow;
			cost += dis[t]*mn_flow;
			for (int i=t;i!=s;i=pre[i]) {
				edg[pre[i]][pre_id[i]].cap -= mn_flow;
				edg[i][edg[pre[i]][pre_id[i]].rev].cap += mn_flow;
			}
//			cout<<"finish2"<<endl;
		}
		return make_pair(cost,flow);
	}
} Flow;

int p[MAX_N];
int q[MAX_N];

typedef long long LL;
const int MAX_P = 1e7 + 6;

int prime[MAX_P];

void build() {
	prime[0] = prime[1]=1;
	for (LL i=2;MAX_P>i;i++) {
		if (prime[i]==0) {
			for (LL j=i*i;MAX_P>j;j+=i) {
				prime[j]=1;
			}
		}
	}
}

bool isPrime(int x) {
	return prime[x]?false:true;
}

int main (){
	build();
	int n;
	scanf("%d",&n);
	set<int> st;
	vector<int> v;
	for (int i=1;n>=i;i++) {
		int x;
		scanf("%d",&x);
		st.insert(x);
		v.push_back(x-1);
		v.push_back(x);
		v.push_back(x+1);
	}
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end()) - v.begin());
	int nn=0;
	int mm=0;
	for (int i:v) {
		int _1 = (st.find(i) == st.end());
		int _2 = (st.find(i-1) == st.end());
		if ((_1^_2)) {
			if (i%2 == 0) p[++nn] = i;
			else q[++mm] = i;
		}
	}
//	cout<<"hihi"<<endl;
//	cout<<"nn = "<<nn<<" , mm = "<<mm<<endl;
	Flow.init(nn+mm+1,0,nn+mm+1);
	for (int i=1;nn>=i;i++) {
		Flow.add_edge(0,i,1,0);
	}
	
	int t=nn+mm+1;
	for (int i=1;mm>=i;i++) {
		Flow.add_edge(i+nn,t,1,0);
	}
	for (int i=1;nn>=i;i++) {
		for (int j=1;mm>=j;j++) {
			if (isPrime(abs(p[i]-q[j]))) Flow.add_edge(i,j+nn,1,1);
			else Flow.add_edge(i,j+nn,1,3);
		}
	}
//	cout<<"hehe"<<endl;
	pii ret=Flow.flow();
	printf("%d\n",ret.first + ((nn-ret.first)/2)*2 + ((mm-ret.first)/2)*2 + 3*((nn-ret.first)%2+(mm-ret.first)%2 )/2);
}


Measured memory_bytes: 39808