#include <bits/stdc++.h>
using namespace std;
const int maxn = 123456;
bool nprime[maxn];
struct he {
  int a, b;
} HMM[maxn];
int n, ai[maxn], bi[maxn];
void init() {
  HMM[2].a = 1;
  HMM[2].b = 1;
  memset(nprime, 0, sizeof(nprime));
  for (int i = 2; i <= 100000; i++) {
    if ((long long)(i)*i > 100000) break;
    for (int j = i; j <= 100000; j++) {
      if ((long long)(i)*j > 100000) break;
      nprime[i * j] = 1;
    }
  }
  for (int i = 1; i <= 100000; i++) HMM[i].a = HMM[i].b = 0;
  for (int i = 1; i <= 100000; i++) {
    if (i + i > 100000) break;
    if (!nprime[i]) {
      for (int j = i; j <= 100000; j++) {
        if (i + j > 100000) break;
        if (!nprime[j]) {
          HMM[i + j].a = i;
          HMM[i + j].b = j;
        }
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &ai[i]);
    bi[ai[i]] = i;
  }
}
vector<int> l, r;
void DYGANDQYM() {
  l.clear();
  r.clear();
  for (int i = n; i >= 2; i--) {
    if (ai[i] != i) {
      int idx = bi[i];
      int com = i - bi[i] + 1;
      if (com == 2) {
        l.push_back(idx);
        r.push_back(i);
        swap(ai[i], ai[idx]);
        swap(bi[ai[i]], bi[ai[idx]]);
      } else {
        if (com % 2 != 0) {
          int a = HMM[com + 1].a;
          int b = HMM[com + 1].b;
          l.push_back(idx);
          r.push_back(idx + a - 1);
          l.push_back(idx + a - 1);
          r.push_back(i);
          swap(ai[idx], ai[idx + a - 1]);
          swap(bi[ai[idx]], bi[ai[idx + a - 1]]);
          swap(ai[idx + a - 1], ai[i]);
          swap(bi[ai[idx + a - 1]], bi[ai[i]]);
        } else {
          l.push_back(idx);
          r.push_back(idx + 1);
          swap(ai[idx], ai[idx + 1]);
          swap(bi[ai[idx]], bi[ai[idx + 1]]);
          idx++;
          int a = HMM[com].a;
          int b = HMM[com].b;
          l.push_back(idx);
          r.push_back(idx + a - 1);
          swap(ai[idx], ai[idx + a - 1]);
          swap(bi[ai[idx]], bi[ai[idx + a - 1]]);
          if (idx + a - 1 != i) {
            l.push_back(idx + a - 1);
            r.push_back(i);
            swap(ai[idx + a - 1], ai[i]);
            swap(bi[ai[idx + a - 1]], bi[ai[i]]);
          }
        }
      }
    }
  }
  printf("%d\n", l.size());
  for (int i = 0; i < l.size(); i++) {
    printf("%d %d\n", l[i], r[i]);
  }
}
int main() {
  while (scanf("%d", &n) != EOF) {
    init();
    DYGANDQYM();
  }
  return 0;
}
