#define STOPIT
#include <bits/stdc++.h>
#define loop(n) for (lint ngtkana_is_a_genius = 0; ngtkana_is_a_genius < lint(n); ngtkana_is_a_genius++)
#define rep(i, begin, end) for (lint i = lint(begin); (i) < lint(end); i++)
#define all(v) v.begin(), v.end()
#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)
using lint = long long;
auto mt = std::mt19937_64(std::random_device{}());
auto cmn = [](auto& a, auto b){ if (a > b) {a = b; return true;} return false; };
auto cmx = [](auto& a, auto b){ if (a < b) {a = b; return true;} return false; };
void debug_impl() { std::cerr << std::endl; }
template <typename Head, typename... Tail>
void debug_impl(Head head, Tail... tail) { std::cerr << " " << head; debug_impl(tail...); }
#ifndef STOPIT
#define debug(...)\
	do {\
		std::cerr << std::boolalpha << "[" << #__VA_ARGS__ << "]:";\
		debug_impl(__VA_ARGS__);\
		std::cerr << std::noboolalpha;\
	} while (false)
#else
#define debug(...) {}
#endif

class bipartite_matching {
		int L, R;
		std::vector<std::vector<int>> graph;
		std::vector<int> match, level;

		bool bfs() {
			std::fill(level.begin(), level.end(), -1);
			std::queue<int> que;
			for (auto i = 0; i < L; i++) {
				if (match.at(i) < 0) {
					level.at(i) = 0;
					que.emplace(i);
				}
			}
			bool ret = false;
			while (!que.empty()) {
				auto crr = que.front(); que.pop();
				for (auto nxt : graph.at(crr)) {
					if (level.at(nxt) != -1) continue;
					level.at(nxt) = level.at(crr) + 1;
					auto w = match.at(nxt);
					if (w == -1)
						{ ret = true; }
					else if (level.at(w) == -1) {
						level.at(w) = level.at(crr) + 1;
						que.emplace(w);
					}
				}
			}
			return ret;
		}

		bool dfs(int crr) {
			for (auto nxt : graph.at(crr)) {
				assert(level.at(nxt) <= level.at(crr) + 1);
				if (level.at(nxt) < level.at(crr) + 1) continue;
				level.at(nxt) = -1;
				auto w = match.at(nxt);
				if (w == -1 || dfs(w)) {
					match.at(nxt) = crr;
					match.at(crr) = nxt;
					level.at(crr) = -1;
					return true;
				}
			}
			level.at(crr) = -1;
			return false;
		}

	public:
		bipartite_matching()=default;
		bipartite_matching(int L, int R):
			L(L), R(R), graph(L + R), match(L + R, -1), level(L + R)
			{}

		void insert(int u, int v) {
			v += L;
			graph.at(u).emplace_back(v);
			graph.at(v).emplace_back(u);
		}


		int build () {
			auto ret = 0;
			while (bfs()) {
				for (int i = 0; i < L; i++) {
					if (match.at(i) == -1 && dfs(i))
						{ ret++; }
				}
			}
			return ret;
		}

		auto collect() const {return match;}

		auto count() const {
			auto k = L + R - std::count(match.begin(), match.end(), -1);
			assert(k % 2 == 0);
			return k / 2;
		}
};

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr>
std::istream& operator>> (std::istream& is, Container& v)
	{ for (auto & x : v) { is >> x; } return is; }

template < typename Container, typename Value = typename Container::value_type, std::enable_if_t<!std::is_same< Container, std::string >::value, std::nullptr_t> = nullptr >
std::ostream& operator<< (std::ostream& os, Container const& v) {
 os << "{";
	for (auto it = v.begin(); it != v.end(); it++)
		{os << (it != v.begin() ? "," : "") << *it;}
	return os << "}";
}

template < class Container, class Value = typename Container::value_type >
auto run_length(Container const& v) {
	auto n = (int)v.size();
	if (n == 0)
		{ return std::vector< std::pair< Value, int > >{}; }
	auto pos = std::vector< int >{};
	for (auto i = 1; i < n; i++) {
		if (v.at(i - 1) != v.at(i))
			{ pos.emplace_back(i); }
	}
	pos.emplace_back(n);
	auto m = (int)pos.size();
	auto len = std::vector< int >(m);
	std::adjacent_difference(pos.begin(), pos.end(), len.begin());
	auto ret = std::vector< std::pair< Value, int > >(m);
	for (auto i = 0; i != m; i++)
		{ ret.at(i) = {v.at(pos.at(i) - 1), len.at(i)}; }
	return ret;
}

template < std::size_t I, typename Container,
	typename Value = typename std::tuple_element_t< I, typename Container::value_type >>
inline auto project(Container const& v) {
	std::vector< Value > ret(v.size());
	std::transform(v.begin(), v.end(), ret.begin(), [](auto&& t){ return std::get< I >(t); });
	return ret;
}

int main() {
	std::cin.tie(0); std::cin.sync_with_stdio(false);
	constexpr int xmax = 10'000'010;
	auto isp = [&] {
		std::vector<int> isp(xmax, true);
		isp.at(0) = false;
		isp.at(1) = false;
		for (lint p = 2; p < (lint)xmax; p++) {
			if (!isp.at(p)) continue;
			for (lint j = 2; j * p < (lint)xmax; j++) {
				isp.at(p * j) = false;
			}
		}
		return isp;
	}();

	int n; std::cin >> n;
	std::vector<int> a(n); std::cin>>a;
	debug(a);

	std::vector<int> ckd(xmax,false);
	for (int x : a) ckd.at(x) = true;
	auto c = project<1>(run_length(ckd));
	debug(c);
	c.pop_back();
	debug(c);
	std::partial_sum(all(c), c.begin());
	assert((int)c.size() % 2 == 0);

	std::vector<std::vector<int>> b(2);
	for (int x : c) {
	  b.at(x%2).emplace_back(x);
	}
	debug(b);
	std::vector<int> sz(2);
	sz.at(0) = b.at(0).size();
	sz.at(1) = b.at(1).size();
	bipartite_matching bm(sz.at(0), sz.at(1));

	rep(i0,0,sz.at(0))
	rep(i1,0,sz.at(1)) {
		debug(i0,i1);
		int x = b.at(0).at(i0);
		int y = b.at(1).at(i1);
		int z = x - y;
		if (z < 0) z = -z;
		if (isp.at(z)) {
			bm.insert(i0, i1);
		}
	}
	bm.build();

	int k = sz.at(0);
	int l = sz.at(1);
	int m = bm.count();
	debug(k,l,m);
	int ans = m + (k-m) + (l-m) + (k-m)%2;
	std::cout << ans << std::endl;
	return 0;
}

Measured memory_bytes: 78464