#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <cstdlib>
#include <memory>
#include <queue>
#include <cassert>
#include <cmath>
#include <ctime>
#include <complex>
#include <bitset>
#include <fstream>
#include <unordered_map>
#include <unordered_set>
#include <numeric>

using namespace std;

#define ws ws_____________________
#define y1 y1_____________________
#define y0 y0_____________________
#define left left_________________
#define right right_______________
#define next next_________________
#define prev prev_________________
#define hash hash_________________

#define pb push_back
#define fst first
#define snd second
#define mp make_pair 
#define sz(C) ((int) (C).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define ford(i, n) for (int i = int(n) - 1; i >= 0; --i)
#define all(C) begin(C), end(C)

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef long double ld;
typedef complex<double> cd;

#ifdef LOCAL
#define eprintf(args...) fprintf(stderr, args), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define FILE_NAME "a"


int n;
vi xs;

bool read() {
	if  (scanf("%d", &n) < 1) {
		return 0;
	}
	xs.resize(n);
	forn(i, n) {
		scanf("%d", &xs[i]);
	}
	return 1;
}

const int MAX = 1e7 + 10;

int A[MAX];
int B[MAX];
bool prime[MAX];

struct Graph {
	vvi g;
	vi mt;
	vi used;
	int n, m;

	Graph() = default;

	Graph(int n, int m) : n(n), m(m) {
		g.resize(n);
	}

	void addE(int v, int to) {
		g[v].pb(to);
	} 

	bool dfs(int v) {
		if  (used[v]) {
			return 0;
		}
		used[v] = 1;
		for (int to : g[v]) {
			if  (mt[to] == -1 || dfs(mt[to])) {
				mt[to] = v;
				return 1;
			}
		}
		return 0;
	}

	vii getMatch() {
		mt.assign(m, -1);
		forn(v, n) {
			used.assign(n, 0);
			dfs(v);
		}

		vii res;
		forn(i, m) {
			if  (mt[i] != -1) {
				res.pb(mp(mt[i], i));
			}
		}
		return res;
	}
};

int calc() {
	vi vals;
	forn(i, MAX) {
		if  (B[i]) {
			vals.pb(i);
		}
	}

	sort(all(vals));
	eprintf("vals:\n");
	for (int val : vals) {
		eprintf("%d ", val);
	}
	eprintf("\n");

	assert(sz(vals) % 2 == 0);

	vi odd;
	vi even;
	for (int val : vals) {
		if  (val & 1) {
			odd.pb(val);
		} else {
			even.pb(val);
		}
	}

	Graph g(sz(odd), sz(even));
	forn(i, sz(odd)) {
		forn(j, sz(even)) {
			const int p = abs(odd[i] - even[j]);
			if  (p >= 3 && prime[p]) {
				g.addE(i, j);
			}
		}
	}

	vii match = g.getMatch();
	int ans = sz(match);

	int cnt_even = sz(even) - sz(match);
	int cnt_odd = sz(odd) - sz(match);

	ans += 2 * (cnt_even / 2);
	cnt_even %= 2;

	ans += 2 * (cnt_odd / 2);
	cnt_odd %= 2;

	assert(cnt_odd == cnt_even);
	if  (cnt_even) {
		ans += 3;
	}

	return ans;
}

int solve() {
	memset (prime, 0, sizeof prime);
	for (int i = 2; i < MAX; ++i) {
		prime[i] = 1;
	}
	for (int i = 2; i < MAX; ++i) {
		if  (prime[i]) {
			for (int j = i + i; j < MAX; j += i) {
				prime[j] = 0;
			}
		}
	}

	memset (A, 0, sizeof A);
	for (int x : xs) {
		A[x] ^= 1;
	}

	forn(i, MAX) {
		B[i] = A[i] ^ A[i + 1];
	}

	int ans = calc();
	return ans;
}

int main() {
#ifdef LOCAL
	freopen(FILE_NAME ".in", "r", stdin);
	// freopen(FILE_NAME ".out", "w", stdout);
#endif

	while (read()) {
		printf("%d\n", solve());
	}

#ifdef LOCAL
	cerr.precision(5);
	cerr << "Time: " << fixed << (double) clock() / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}


Measured memory_bytes: 88192