#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
#define SIZE 222
#define INF 1000000
typedef pair<int, int>pii;
class maxflow
{
public:
	vector<int>pat[SIZE];
	vector<int>cap[SIZE];
	vector<int>rev[SIZE];
	bool flag[SIZE];
	int dist[SIZE];
	int now[SIZE], ind[SIZE];
	int idx[SIZE];
	int flow;
	int gd;
	void adde(int s, int t, int cp)//多重辺は消してから s->tの容量cpの辺をはる
	{
		pat[s].push_back(t);
		pat[t].push_back(s);
		cap[s].push_back(cp);
		cap[t].push_back(0);
		rev[s].push_back(pat[t].size() - 1);
		rev[t].push_back(pat[s].size() - 1);
	}
	void blockflow(int node, int len, int go, int pt)//ブロックフローを求めて流す
	{
		if (pt == len)
		{
			if (node != go)return;
			int mini = INF, rr = -1;
			for (int i = 0; i < pt; i++)if (cap[now[i]][ind[i]] < mini)mini = cap[now[i]][ind[i]], rr = i;
			for (int i = 0; i < pt; i++)cap[now[i]][ind[i]] -= mini, cap[pat[now[i]][ind[i]]][rev[now[i]][ind[i]]] += mini;
			flow += mini;//mini==INFになったら非有界
			gd = rr;
			return;
		}
		now[pt] = node;
		for (int i = idx[node]; i < pat[node].size(); i++)
		{
			if (dist[pat[node][i]] == dist[node] + 1 && cap[node][i]>0)
			{
				ind[pt] = i;
				blockflow(pat[node][i], len, go, pt + 1);
				if (gd < pt)break;
				else gd = INF;
			}
			idx[node]++;
		}
	}
	void dinic(int st, int go, int num)//dinicのアルゴリズムで最大流を求める 変数flowにmaxflowの値が入る
	{
		flow = 0;
		for (;;)
		{
			queue<pii>que;
			fill(dist, dist + num, INF);
			fill(flag, flag + num, false);
			que.push(make_pair(st, 0));
			for (;;)
			{
				if (que.empty())break;
				pii z = que.front();
				que.pop();
				if (flag[z.first])continue;
				flag[z.first] = true;
				dist[z.first] = z.second;
				for (int i = 0; i < pat[z.first].size(); i++)
				{
					if (dist[pat[z.first][i]]>z.second + 1 && cap[z.first][i] > 0)
					{
						dist[pat[z.first][i]] = z.second + 1;
						que.push(make_pair(pat[z.first][i], z.second + 1));
					}
				}
			}
			if (dist[go] == INF)return;
			gd = INF;
			fill(idx, idx + SIZE, 0);
			blockflow(st, dist[go], go, 0);
		}
	}
	vector<int>getcut(int st, int go, int num)//頂点iがmincutのst側なら1 そうでなければ0
	{
		dinic(st, go, num);
		vector<int>ret;
		for (int i = 0; i < num; i++)ret.push_back(flag[i]);
		return ret;
	}
};
maxflow gr;
bool np[10101010];
int d[111];
int main()
{
	int num;
	scanf("%d", &num);
	for (int i = 0; i < num; i++)scanf("%d", &d[i]);
	vector<int>zv;
	for (int i = 0; i < num; i++)
	{
		if (i == 0)zv.push_back(d[i]);
		else if (d[i - 1] + 1 != d[i])zv.push_back(d[i]);
		if (i == num - 1)zv.push_back(d[i] + 1);
		else if (d[i + 1] - 1 != d[i])zv.push_back(d[i] + 1);
	}
	vector<int>v1, v2;
	for (int i = 0; i < zv.size(); i++)
	{
		if (zv[i] % 2 == 0)v1.push_back(zv[i]);
		else v2.push_back(zv[i]);
	}
	np[1] = true;
	for (int i = 2; i <= 10000000; i++)
	{
		if (np[i])continue;
		for (int j = i + i; j <= 10000000; j += i)np[j] = true;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		for (int j = 0; j < v2.size(); j++)
		{
			int t = v2[j] - v1[i];
			if (t < 0)t = -t;
			if (!np[t])gr.adde(2 + i, 2 + num + j, 1);
		}
	}
	for (int i = 0; i < num; i++)gr.adde(0, i + 2, 1), gr.adde(i + num + 2, 1, 1);
	gr.dinic(0, 1, 202);
	int r = gr.flow;
	int a = v1.size() - r, b = v2.size() - r;
	if ((v1.size() - r) % 2)r++;
	printf("%d\n", r + a + b);
}

Measured memory_bytes: 10240