#include <cstdio>
#include <utility>
#include <vector>
#include <cmath>
#include <queue>
#include <cstring>
#include <cstdlib>

using namespace std;
typedef pair<int,int> P;

int N;
int x[110];
int y[210];
bool isPrimeNumber(int x) {
  if (x<=2) {
    return false;
  }
  for(int i=2;i<=sqrt(x)+1;++i) {
    if (x%i==0) {
      return false;
    }
  }
  return true;
}
class Dinic {
public:
  struct Edge{
    int from,to,capacity,flow;
    int calcRest(bool isRev) {
      return isRev ? flow : capacity-flow;
    }
    int getNext(bool isRev) {
      return isRev ? from : to;
    }
  };
  static const int MAX_E=100000;
  static const int MAX_V=500;
  static const int INF=1000000;
  int levels[MAX_V];
  Edge edgeInstances[MAX_E];
  vector<Edge*> edges[MAX_V][2]; // 1 => reverse edge
  int E=0;

  void addEdge(Edge edge) {
    edgeInstances[E] = edge;
    edges[edge.from][0].push_back(&edgeInstances[E]);
    edges[edge.to][1].push_back(&edgeInstances[E]);
    E++;
  }

  bool setLevels(int s, int t) {
    memset(levels,-1,sizeof(levels));
    queue<int> Q;
    Q.push(s);
    levels[s] = 0;
    while(!Q.empty()) {
      int current = Q.front();
      Q.pop();
      if(current==t) {
        return true;
      }

      for(int j=0;j<2;++j) {
        bool revEdge = j == 1;
        vector<Edge*>& edgeList=edges[current][j];
        for(int i=0;i<edgeList.size();++i) {
          Edge& edge = *edgeList[i];
          int rest = edge.calcRest(revEdge), next = edge.getNext(revEdge);
          if(levels[next]!=-1) continue;
          if(rest > 0){
            levels[next] = levels[current] + 1;
            Q.push(next);
          }
        }
      }
    }
    return false;
  }

  int calcMaxFlow(int s, int t) {
    int max_flow=0;
    while(true) {
      bool continueFlag = setLevels(s,t);
      if(!continueFlag) {
        break;
      }
      while(true) {
        int flow = findFlow(s, t, INF);
        max_flow += flow;
        if(flow==0) {
          break;
        }
      }
    }
    return max_flow;
  }

  int findFlow(int current, int destination, int flow) {
    if(current == destination) return flow;

    for(int j=0;j<2;++j) {
      bool revEdge = j == 1;
      vector<Edge*>& edgeList=edges[current][j];
      for(int i=0;i<edgeList.size();++i) {
        Edge& edge = *edgeList[i];
        int rest = edge.calcRest(revEdge), next = edge.getNext(revEdge);
        if(levels[next]<=levels[current])continue;
        if(rest > 0){
          int max_flow = findFlow(next, destination, min(rest,flow));
          edge.flow += revEdge ? -max_flow: max_flow;
          if(max_flow>0) {
            return max_flow;
          }
        }
      }
    }
    return 0;
  }

};

Dinic dinic;
int main() {
  int num=0;
  int numEven=0;
  int numOdd=0;
  memset(y,0,sizeof(y));
  memset(x,-1,sizeof(x));
  scanf("%d", &N);
  for(int i=0;i<N;++i) {
    scanf("%d", &x[i]);
  }
  for(int i=0;i<N;++i) {
    if (i==0) {
      y[num++] = x[i];
    } else if(x[i-1]!=x[i]-1) {
      y[num++] = x[i];
    }
    if (x[i]!=x[i+1]-1) {
      y[num++] = x[i]+1;
    }
  }
  for(int i=0;i<num;++i) {
    if(y[i]%2==0) {
      numEven++;
    } else {
      numOdd++;
    }
  }
  for(int i=0;i<num;++i) {
    dinic.addEdge({0,i+1,1,0});
    dinic.addEdge({201+i,450,1,0});
    for(int j=0;j<num;++j) {
      if(y[i]%2==1 && y[j]%2==0 && isPrimeNumber(abs(y[j]-y[i]))) {
        dinic.addEdge({i+1,201+j,1,0});
      }
    }
  }
  int maxk=dinic.calcMaxFlow(0, 450);
  printf("%d\n", maxk + ((numEven-maxk)/2+(numOdd-maxk)/2)*2 + ((numEven-maxk)%2) * 3);

  return 0;
}


Measured memory_bytes: 512