#include<bits/stdc++.h>
#define int long long
#define X first
#define Y second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
template<class T> using vv = vector<vector<T>>;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
bool is_composite[11451419];
map<int, char> mp;

struct wg{
  template<class T> using vv = vector<vector<T>>;
	struct edge{
		int u, v, w;
		edge(int u=-1, int v=-1, int w = 0) : u(u), v(v), w(w) {}
	};

	const int inf = 1e9;

	vv<edge> g;
	int n; //n%2==0
	vector<int> label, pa, slackpa, bel, tp, vis, match;
	queue<int> q;
	vv<int> flower,flower_from;

	int e_delta(const edge& e) { //does not work inside blossoms
		return label[e.u] + label[e.v] - g[e.u][e.v].w * 2;
	}
	void update_slackpa(int u, int x) {
		if (slackpa[x]==-1 || e_delta(g[u][x]) < e_delta(g[slackpa[x]][x])) slackpa[x] = u;
	}
	void set_slackpa(int x) {
		slackpa[x] = -1;
    rep(u, n) if (bel[u] != x && tp[bel[u]] == 0) update_slackpa(u,x);
	}
	void q_push(int u) {
		if (u < n) q.push(u);
		else for (int v : flower[u]) q_push(v);
	}
	void set_st(int x, int b) {
		bel[x] = b;
		if (x >= n) for (int v : flower[x]) set_st(v, b);
	}
	int get_pr(int b, int xr) {
		int pr = find(all(flower[b]), xr) - flower[b].begin();
		if (pr%2) {
			reverse(flower[b].begin()+1, flower[b].end());
			pr = (int)flower[b].size()-pr;
		}
		return pr;
	}
	void set_match(int u, int v) {
		match[u] = g[u][v].v;
		if (u>=n) {
			edge e = g[u][v];
			int xr = flower_from[u][e.u];
			int pr = get_pr(u, xr);
      rep(i, pr) {
        set_match(flower[u][i], flower[u][i^1]);
      }
			set_match(xr, v);
			rotate(flower[u].begin(), flower[u].begin()+pr, flower[u].end());
		}
	}
	void augment(int u, int v) {
		while (1) {
			int xnv = -1;
			if (match[u] != -1) xnv = bel[match[u]];
			set_match(u,v);
			if (xnv == -1) return;
			set_match(xnv, bel[pa[xnv]]);
			u = bel[pa[xnv]];
			v = xnv;
		}
	}
	int get_lca(int u, int v) {
		static int t=0;
		for (++t; u!=-1 || v!=-1; swap(u,v)) {
			if (u == -1) continue;
			if (vis[u] == t) return u;
			vis[u] = t;
			if (match[u] == -1) {
				u = -1;
				continue;
			}
			u = bel[match[u]];
			if (u!=-1) u = bel[pa[u]];
		}
		return -1;
	}
	void add_blossom(int u, int lca, int v) {
		int b = n;
		while(!flower[b].empty()) b++;

		label[b] = 0;
		tp[b] = 0;
		match[b] = match[lca];
		flower[b].clear();
		flower[b].push_back(lca);

    int y;
		for(int x=u; x!=lca; x = bel[pa[y]]){
			flower[b].push_back(x);
			flower[b].push_back(y = bel[match[x]]);
			q_push(y);
		}
		reverse(flower[b].begin()+1,flower[b].end());
		for(int x=v; x!=lca; x = bel[pa[y]]){
			flower[b].push_back(x);
			flower[b].push_back(y = bel[match[x]]);
			q_push(y);
		}
		set_st(b, b);
    rep(x, 2*n) {
      g[b][x] = g[x][b]= edge();
    }
    rep(x, n) {
      flower_from[b][x] = -1;
    }
    for (int xs : flower[b]) {
      rep(x, 2*n) {
				if (g[b][x].u == -1 || e_delta(g[xs][x]) < e_delta(g[b][x])) {
          g[b][x] = g[xs][x];
          g[x][b] = g[x][xs];
        }
			}
      rep(x, n) if(flower_from[xs][x] != -1) flower_from[b][x] = xs;
		}
		set_slackpa(b);
	}
	void expand_blossom(int b) { //tp[b] == 1
    for (int v : flower[b]) set_st(v, v);
		int xr = flower_from[b][g[b][pa[b]].u];
		int pr = get_pr(b, xr);
		for (int i=0; i<pr; i+=2) {
			int xs = flower[b][i];
			int xns = flower[b][i+1];
			pa[xs] = g[xns][xs].u;
			tp[xs] = 1;
			tp[xns] = 0;
			slackpa[xs] = -1;
			set_slackpa(xns);
			q_push(xns);
		}
		tp[xr] = 1;
		pa[xr] = pa[b];
		for (int i=pr+1; i<flower[b].size(); i++) {
			int xs = flower[b][i];
			tp[xs] = -1;
			set_slackpa(xs);
		}
		bel[b] = -1;
		match[b] = -1;
		flower[b].clear();
	}
	bool found_edge(const edge& e) {
		int u = bel[e.u];
		int v = bel[e.v];
		if (tp[v]==-1) {
			tp[v] = 1;
			pa[v] = e.u;
			int nu = bel[match[v]];
			slackpa[v] = slackpa[nu] = -1;
			tp[nu] = 0;
			q_push(nu);
		} else if (tp[v]==0) {
			int lca = get_lca(u,v);
			if(lca == -1){
				augment(u,v);
				augment(v,u);
				return true;
			} else add_blossom(u,lca,v);
		}
		return false;
	}
	bool matching() {
		tp.assign(2*n,-1);
		slackpa.assign(2*n,-1);
		q = queue<int>();
    rep(i, 2*n) {
      if (bel[i] == i && match[i] == -1) {
			  tp[i] = 0;
			  pa[i] = -1;
			  q_push(i);
      }
		}

		if(q.empty()) return false;

		while (1) {
			while (!q.empty()) {
				int u = q.front(); q.pop();
				if (tp[bel[u]] == 1) continue;
        rep(v, n) {
					if (bel[u] != bel[v]) {
						if (e_delta(g[u][v]) == 0) {
							if (found_edge(g[u][v])) return true;
						} else update_slackpa(u, bel[v]);
					}
				}
			}
			int d = inf;
      reps(b, n, 2*n) {
        if (bel[b] == b && tp[b] == 1) d = min(d, label[b]/2);
      }
      rep(x, 2*n) {
			  if (bel[x] == x && slackpa[x] != -1) {
				  if (tp[x] == -1)    d = min(d, e_delta(g[slackpa[x]][x]));
				  else if (tp[x] == 0) d = min(d, e_delta(g[slackpa[x]][x])/2);
        }
			}
      rep(u, n) {
				if (tp[bel[u]] == 0) label[u] -= d;
				else if (tp[bel[u]] == 1) label[u] += d;
			}
      reps(b, n, 2*n) {
				if (bel[b] == b) {
					if (tp[b] == 0) label[b] += d*2;
					else if (tp[b] == 1) label[b] -= d*2;
				}
			}
      reps(b, n, 2*n) {
				if (bel[b] == b && tp[b]==1 && label[b]==0) expand_blossom(b);
      }
      rep(x, 2*n) {
				if (bel[x] == x && slackpa[x] != -1 && bel[slackpa[x]] != x && e_delta(g[slackpa[x]][x]) == 0) {
					if(found_edge(g[slackpa[x]][x])) return true;
        }
      }
		}
	}
	void init_g(vv<int> &weight){
		int sz = (int)weight.size();
		n = sz+sz%2;
		g.assign(2*n, vector<edge>(2*n, edge()));
    rep(i, n) {
      rep(j, n) {
				if (i < sz && j < weight[i].size()) g[i][j] = edge(i, j, weight[i][j]);
				else g[i][j] = edge(i, j, 0);
			}
		}
	}
	LL solve(){
		label.assign(2*n,0);
		pa.assign(2*n,-1);
		match.assign(2*n,-1);
		vis.assign(2*n,0);
		flower.assign(2*n,vector<int>());
		flower_from.assign(2*n,vector<int>(n,-1));
		bel.assign(2*n,-1);
    rep(i, n) {
      bel[i] = i;
		  flower_from[i][i] = i;
    }
		int w_max = -inf;
    rep(i, n) {
      rep(j, n) {
				if (i == j) continue;
				w_max = max(w_max, g[i][j].w);
			}
		}
    rep(i, n) label[i] = w_max;
		while (matching());
		LL re = 0LL;
    rep(i, n) {
			assert(match[i] != -1);
			if (match[i] > i) re += 1LL*g[i][match[i]].w;
		}
		return re;
	}
};

int GetCost(int d) {
  if (d == 2) return 2;
  if (!is_composite[d]) return 1;
  if (d%2 == 0) return 2;
  return 3;
}

signed main(){
  is_composite[1] = true;
  reps(i, 2, 11451419) {
    if (is_composite[i]) continue;
    for (int j=i+i; j<11451419; j+=i) {
      is_composite[j] = true;
    }
  }

  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);

  cin >> N;

  rep(i, N) {
    int x;
    cin >> x;
    mp[x] ^= 1;
    mp[x+1] ^= 1;
  }

  vector<int> vs;
  for (auto &p : mp) {
    if (p.Y == 0) continue;
    vs.eb(p.X);
  }
  int m = vs.size();
  assert(m%2 == 0);
  vv<int> G(m);
  rep(i, m) {
    G[i].resize(m);
    rep(j, m) {
      if (i == j) continue;
      G[i][j] = 10000-GetCost(abs(vs[i]-vs[j]));
    }
  }
  wg match;
  match.init_g(G);
  //cout << match.solve() << endl;
  cout << 10000*(m/2)-match.solve() << endl;
}


Measured memory_bytes: 16256