#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

// Maximal prime value
const int MAXVAL = 1e7 + 5;

struct erat_sieve{
	char is_p[MAXVAL];
	int top_p;

	void get_primes(){
		is_p[0] = is_p[1] = 1;
		for(int i = 2; i * i < MAXVAL; i++){
			if (!is_p[i]){
				for(int j = i * i; j < MAXVAL; j += i){
					is_p[j] = 1;
				}
			}
		}
	}
} erat;

const int MAXN = 2e2 + 5;

struct graph {
	// Number of vertices for two parts
	int n1, n2;
	
	// graph (1 -> 2)
	vi g[MAXN];
	
	// Col for Kuhn series (1st part)
	int col[MAXN];
	
	// Current color for Kuhn series
	int cur_col;
	
	// Nxt for Kuhn (2nd part)
	int nxt[MAXN];
	
	// Final matching
	vector<pii> matching;
	
	// Adding edge
	void add_edge(int a, int b){		
		g[a].pb(b);
	}	
	
	// Try_kuhn
	int try_kuhn(int s){
		if (col[s] == cur_col){
			return 0;
		}
		col[s] = cur_col;
		REP(i, 0, SZ(g[s])){
			int to = g[s][i];
			if (!nxt[to] || try_kuhn(nxt[to])){
				nxt[to] = s;
				return 1;
			}
		}
		return 0;
	}
	
	// Set random matching for speeding up Kuhn
	void set_random_matching(){
		REPN(i, 1, n1){
			if (col[i] == 0){
				REP(j, 0, SZ(g[i])){
					int to = g[i][j];
					if (nxt[to] == 0){
						col[i] = 1;
						nxt[to] = i;
						break;
					}
				}
			}
		}
	}
	
	// Find matching
	void get_matching(){
		// Init
		REPN(i, 1, n1){
			col[i] = 0;
		}
		REPN(i, 1, n2){
			nxt[i] = 0;
		}
		matching.clear();
		
		// Random matching
		cur_col = 1;
		set_random_matching();
						
		// Go Kuhn
		REPN(i, 1, n1){
			if (col[i] == 0){
				cur_col++;
				try_kuhn(i);
			}
		}
		
		// Restore matching
		REPN(i, 1, n2){
			if (nxt[i] != 0){
				matching.pb(mp(nxt[i], i));
				//printf("%d %d\n", i, nxt[i]);
			}
		}
	}	
} gg;

vi v0, v1, vals;

int v[MAXN];

void solve(){
	erat.get_primes();	
	int n;
	scanf("%d", &n);
	REP(i, 0, n){
		scanf("%d", &v[i]);
	}
	for(int i = 0; i < n; ){
		int j;
		for(j = i + 1; j < n && j - i == v[j] - v[i]; j++);
		j--;
		vals.pb(v[i]);
		vals.pb(v[j] + 1);
		i = j + 1;
	}
	REP(i, 0, SZ(vals)){
		if (vals[i] % 2 == 0){
			v0.pb(vals[i]);
		} else {
			v1.pb(vals[i]);
		}
	}
	gg.n2 = SZ(v0);
	gg.n1 = SZ(v1);
	REP(i, 0, gg.n1){
		REP(j, 0, gg.n2){
			int tmp = v1[i] - v0[j];
			if (tmp < 0){
				tmp = -tmp;
			}
			if (!erat.is_p[tmp]){
				gg.add_edge(i + 1, j + 1);
				//printf("%d %d\n", v1[i], v0[j]);
			}
		}
	}
	gg.get_matching();
	int cnt_m = SZ(gg.matching);
	int cnt_1 = gg.n1 - cnt_m;
	int cnt_2 = gg.n2 - cnt_m;
	int ans = cnt_m + (cnt_1 + cnt_1 % 2) + (cnt_2);
	printf("%d\n", ans);
	//printf("%d\n", cnt_m);	
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 10112