//#include "stdafx.h"
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <tuple>
#include <numeric>
#include <assert.h>
#include <functional>
#include <unordered_map>

using namespace std;

/*-----------------------------------------------------------------------------
　定義
 -------------------------------------------------------------------------------*/
#define REP(i, n)				for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n)			for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define INF						2e9
#define MOD						(1000 * 1000 * 1000 + 7)
#define Ceil(x, n)				(((((x))+((n)-1))/n))		/* Nの倍数に切り上げ割り算 */
#define CeilN(x, n)				(((((x))+((n)-1))/n)*n)		/* Nの倍数に切り上げ */
#define FloorN(x, n)			((x)-(x)%(n))				/* Nの倍数に切り下げ */
#define IsOdd(x)				(((x)&0x01UL) == 0x01UL)			
#define IsEven(x)				(!IsOdd((x)))						
#define ArrayLength(x)			(sizeof( x ) / sizeof( x[ 0 ]))
#define	MAX_QWORD				((QWORD)0xFFFFFFFFFFFFFFFF)
#define M_PI					3.14159265358979323846
typedef long long				ll;
typedef unsigned long long int	QWORD;
typedef pair<ll, ll>			P;

/*-----------------------------------------------------------------------------
　処理
 -------------------------------------------------------------------------------*/
// 枝定義
struct Edge
{
	int	toIdx;
	int	revIdx;
	int	cap;
	Edge(){}
	Edge(int to, int rev, int capArg): toIdx(to), revIdx(rev), cap(capArg){}
};

// グラフ定義(二次元配列)
using Graph = vector<vector<Edge>>;
 
// フォード・ファルカーソン
class FordFulkerson 
{
private:
	int V;
	Graph G;
	vector<bool> isUsed;

private:
	int dfs(int from, int sinkPos, int flow)
	{
		if (from == sinkPos) {
			return flow;
		}

		int flowOne = 0;
		isUsed[from] = true;
		for (Edge &edge : G[from]) {
			int to = edge.toIdx;
			if (!isUsed[to]) {
				if (0 < edge.cap) {
					flowOne = dfs(to, sinkPos, min(flow, edge.cap));
					if (0 < flowOne) {
						edge.cap -= flowOne;
						G[to][edge.revIdx].cap += flowOne;
						break;
					}
				}
			}
		}
		return flowOne;
	}

public:
	FordFulkerson(int N)
	{
		G.resize(N);
	}

	// 枝を追加
	void AddEdge(int from, int to, int cap)
	{
		int revIdxTo = G[to].size();
		int revIdxFrom = G[from].size();
		G[from].emplace_back(to, revIdxTo, cap);
		G[to].emplace_back(from, revIdxFrom, 0);
	}

	// 最大フローを求める
	int GetMaxFlow(int startPos, int endPos)
	{
		int maxFlow = 0;
		V = (int)G.size();
		isUsed.resize(V);
		for (;;) {
			fill(isUsed.begin(), isUsed.end(), false);
			int flowOne = dfs(startPos, endPos, (int)INF);
			if (flowOne == 0) {
				break;
			}
			maxFlow += flowOne;
		}
		return maxFlow;
	}
};

/* 素数判定 */
bool isPrime(ll p) 
{
	for (ll i = 2; i <= sqrt(p); i++) if (p % i == 0) return false;
	return p > 1;
}

int main()
{
	int N;
	cin >> N;
	vector<int> x(N);
	map<int, int> y;
	REP(i, N) cin >> x[i];
	REP(i, N) {
		y[x[i]]++;
		y[x[i] + 1]++;
	}

	vector<int> odd;
	vector<int> even;
	for (auto it = y.begin(); it != y.end(); it++) {
		if (IsOdd(it->second)) {
			if (IsEven(it->first)) {
				even.emplace_back(it->first);
			} else {
				odd.emplace_back(it->first);
			}
		}
	}

	// 始点→偶数
	FordFulkerson res(4 * 1000);
	int start = 0;
	REP(i, even.size()) {
		res.AddEdge(start, 1000 + i, 1);
	}
	
	// 奇数→終点
	int end = 1;
	REP(i, odd.size()) {
		res.AddEdge(2000 + i, 1, 1);
	}
	
	// 偶数→奇数(素数)
	REP(i, even.size()) {
		REP(j, odd.size()) {
			if (isPrime(abs(even[i] - odd[j]))) {
				res.AddEdge(1000 + i, 2000 + j, 1);
			}
		}
	}
	
	// 最大流量
	int primeCnt = res.GetMaxFlow(start, end);
	
	// 残りは貪欲
	int evenCnt = (even.size() - primeCnt) / 2 + (odd.size() - primeCnt) / 2;
	int oddCnt = (even.size() - primeCnt) % 2;

	cout << primeCnt + evenCnt * 2 + oddCnt * 3 << endl;
	return 0;
}



Measured memory_bytes: 512