#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define sar(a,n) {cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl;}

using namespace std;

template<typename S,typename T>auto&operator<<(ostream&o,pair<S,T>p){return o<<"{"<<p.fi<<","<<p.se<<"}";}
template<typename T>auto&operator<<(ostream&o,set<T>s){for(auto&e:s)o<<e<<" ";return o;}
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,priority_queue<S,T,U>q){while(!q.empty())o<<q.top()<<" ",q.pop();return o;}
template<typename K,typename T>auto&operator<<(ostream&o,map<K,T>&m){for(auto&e:m)o<<e<<" ";return o;}
template<typename T>auto&operator<<(ostream&o,vector<T>v){for(auto&e:v)o<<e<<" ";return o;}
void ashow(){cout<<endl;}template<typename T,typename...A>void ashow(T t,A...a){cout<<t<<" ";ashow(a...);}
template<typename S,typename T,typename U>
struct TRI{S fi;T se;U th;TRI(){}TRI(S f,T s,U t):fi(f),se(s),th(t){}
bool operator<(const TRI&_)const{return(fi==_.fi)?((se==_.se)?(th<_.th):(se<_.se)):(fi<_.fi);}};
template<typename S,typename T,typename U>
auto&operator<<(ostream&o,TRI<S,T,U>&t){return o<<"{"<<t.fi<<","<<t.se<<","<<t.th<<"}";}

typedef pair<int, int> P;
typedef pair<ll, ll> pll;
typedef TRI<int, int, int> tri;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<P> vp;
typedef vector<double> vd;
typedef vector<string> vs;

const int MAX_N = 10000005;

bool x[MAX_N];
bool is_prime[MAX_N];

void sieve(){
	for(int i=0;i<MAX_N;i++){
		is_prime[i] = true;
	}
	is_prime[0] = is_prime[1] = false;
	for(int i=2;i<MAX_N;i++){
		if(is_prime[i]){
			for(int j=2*i;j<MAX_N;j+=i){
				is_prime[j] = false;
			}
		}
	}
}

class BM {
private:
    struct edge {
        int to,cap,rev;
    };
    int U,V;
    vector<vector<edge> > G;
    vector<int> level;
    vector<int> iter;

public:
    BM(int u,int v) : U(u), V(v), G(U+V+2){
        for(int i = 0; i < U; i++){
            init_edge(0,i+1);
        }
        for(int i = 0; i < V; i++){
            init_edge(U+i+1,U+V+1);
        }
    }
    void init_edge(int from,int to) {
        G[from].push_back((edge){to,1,(int)G[to].size()});
    	G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }
    void add_edge(int from,int to) {
        from += 1,to += U+1;
    	G[from].push_back((edge){to,1,(int)G[to].size()});
    	G[to].push_back((edge){from,0,(int)G[from].size()-1});
    }
    void bfs(int s) {
        fill(level.begin(),level.end(),-1);
    	queue<int> que;
    	level[s] = 0;
    	que.push(s);
    	while(!que.empty()){
            int v = que.front();
            que.pop();
            for(auto& e : G[v]){
                if(e.cap > 0 && level[e.to] < 0){
                    level[e.to] = level[v] + 1;
                    que.push(e.to);
                }
            }
        }
    }
    int dfs(int v,int t,int f) {
        if(v==t){
            return f;
        }
        for(int &i = iter[v];i<(int)G[v].size();i++){
            edge &e = G[v][i];
            if(e.cap > 0 && level[v] < level[e.to]){
                int d = dfs(e.to,t,min(f,e.cap));
                if(d>0){
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
    int solve() {
        level.resize(U+V+2), iter.resize(U+V+2);
        int flow = 0;
        int s=0,t=U+V+1;
        for(;;){
            bfs(s);
            if(level[t] < 0) return flow;
            fill(iter.begin(),iter.end(),0);
            int f;
            while((f=dfs(s,t,numeric_limits<int>::max())) > 0){
                flow += f;
            }
        }
    }
    vector<int> allocate() {
        vector<int> res(U, -1);
        for(int i = 0; i < U; i++){
            for(auto& e : G[i+1]){
                if(e.cap == 0 && e.to != 0){
                    res[i] = e.to-U-1;
                    break;
                }
            }
        }
        return res;
    }
};

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    sieve();
    rep(i,n){
        int u;
        cin >> u;
        x[u] = true;
    }
    vector<int> val1, val2;
    srep(i,1,MAX_N){
        if(x[i-1] ^ x[i]){
            if(i % 2) val1.pb(i);
            else val2.pb(i);
        }
    }
    const int a = (int)val1.size(), b = (int)val2.size();
    if(a == 0 || b == 0){
        cout << (a + b) / 2 * 2 + (a % 2) << "\n";
        return 0;
    }
    BM bm(a, b);
    rep(i,a){
        rep(j,b){
            if(is_prime[abs(val1[i] - val2[j])]){
                bm.add_edge(i, j);
            }
        }
    }
    const int res = bm.solve();
    cout << res + (a + b - 2 * res) / 2 * 2 + ((a - res) % 2) << "\n";
    return 0;
}

Measured memory_bytes: 18816