#define C
typedef long long readtype;

/* Header {{{ */
#ifdef C
#include <stdio.h>
#include <math.h>
#include <string.h>
#define isdigit(a) ((a) >= '0' && (a) <= '9' ? true : false)
template<typename type> type abs(type a) { return a < 0 ? -a : a; }
template<typename type> type min(type a, type b) { return a < b ? a : b; }
template<typename type> type beMin(type &a, type b) { return a = (a < b ? a : b); }
template<typename type> type max(type a, type b) { return a > b ? a : b; }
template<typename type> type beMax(type &a, type b) { return a = (a > b ? a : b); }
template<typename type> void swap(type &a, type &b) { type c; c = a; a = b; b = c; }
#endif

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

typedef long long var;

readtype read() {
  readtype a = 0, c = getchar(), s = 0;
  while (!isdigit(c)) s |= c == '-', c = getchar();
  while (isdigit(c)) a = a * 10 + c - 48, c = getchar();
  return s ? -a : a;
}
/* }}} */

const int N = 11004;
const int M = 1100006;
const int X = 1e7;
const int INF = 0x3f3f3f3f;

int n, m, x[N];
bool mark[X + 10];
int cnt, prime[X];
bool notprime[X + 10];
int top = 1, fi[N], ne[M], to[M], fl[M];
int S, T;
int head, tail, q[N], deep[N];
int cur[N];

void add(int u, int v, int w);
int Dinic();
bool BFS();
int DFS(int t, int f);

int main() {
  /*
#ifndef ONLINE_JUDGE
  freopen("arc080d.in", "r", stdin);
  freopen("arc080d.out", "w", stdout);
#endif
*/
  notprime[1] = true;
  for (int i = 2; i <= X; ++i) {
    if (!notprime[i]) prime[++cnt] = i;
    for (int j = 1; j <= cnt; ++j) {
      if (prime[j] * i > X) break;
      notprime[prime[j] * i] = true;
      if (!(i % prime[j])) break;
    }
  }
  for (int i = read(); i >= 1; --i) mark[read()] = true;
  for (int i = 1; i <= X + 1; ++i) {
    if (mark[i] ^ mark[i - 1]) x[++n] = i;
  }
  S = n + 1, T = n + 2;
  int oddNum = 0, evenNum = 0;
  for (int i = 1; i <= n; ++i) {
    if (!(x[i] % 2)) add(i, T, 1), evenNum++;
    else add(S, i, 1), oddNum++;
  }
  for (int i = 1; i <= n; ++i) {
    if (!(x[i] % 2)) continue;
    for (int j = 1; j <= n; ++j) {
      if (x[j] % 2 || notprime[abs(x[i] - x[j])]) continue;
      add(i, j, 1);
      // printf("%d %d %d\n", x[i], x[j], x[i] - x[j]);
    }
  }

  /*
  for (int i = 1; i <= n; ++i) printf("%d ", x[i]);
  puts("");
  */

  int k = Dinic();
  int res = k + ((evenNum - k) / 2 + (oddNum - k) / 2) * 2 + ((evenNum - k) % 2) * 3;
  printf("%d\n", res);
  return 0;
}

void add(int u, int v, int w) {
  ne[++top] = fi[u], fi[u] = top, to[top] = v, fl[top] = w;
  ne[++top] = fi[v], fi[v] = top, to[top] = u, fl[top] = 0;
  // printf("%d %d %d\n", u, v, w);
}

int Dinic() {
  int res = 0;
  while (BFS()) {
    for (int i = 1; i <= T; ++i) cur[i] = fi[i];
    res += DFS(S, INF);
  }
  return res;
}

bool BFS() {
  memset(deep, 0, sizeof(deep));
  q[head = tail = 1] = S;
  deep[S] = 1;
  while (head <= tail) {
    int f = q[head++];
    for (int i = fi[f]; i; i = ne[i]) {
      if (deep[to[i]] || !fl[i]) continue;
      deep[to[i]] = deep[f] + 1;
      q[++tail] = to[i];
    }
  }
  return deep[T];
}

int DFS(int t, int f) {
  if (t == T) return f;
  int sumflow = 0;
  for (int &i = cur[t]; i; i = ne[i]) {
    if (deep[to[i]] != deep[t] + 1 || !fl[i]) continue;
    int tflow = DFS(to[i], min(fl[i], f - sumflow));
    sumflow += tflow;
    fl[i] -= tflow, fl[i ^ 1] += tflow;
  }
  return sumflow;
}


Measured memory_bytes: 28928