#include <bits/stdc++.h>
using namespace std;
int n, a[100005], b[100005], mark[100005], p[10005], e;
int duqu() {
  int s = 0;
  char c = getchar();
  while (c < '0' || c > '9') getchar();
  while (c >= '0' && c <= '9') {
    s = s * 10 + c - '0';
    c = getchar();
  }
  return s;
}
void shaifa() {
  for (int i = 2; i * i <= n; i++) {
    if (mark[i]) continue;
    for (int j = i * i; j <= n; j += i) {
      mark[j] = 1;
    }
  }
  for (int i = 2; i <= n; i++)
    if (!mark[i]) {
      p[++e] = i;
    }
}
int ans = 0, w[500005][2];
int main() {
  n = duqu();
  shaifa();
  for (int i = 1; i <= n; i++) {
    a[i] = duqu();
    b[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (b[i] == i) continue;
    int L = b[i] - i + 1, d = b[i];
    while (L) {
      int z = 0, y = e, zj;
      while (z + 1 != y) {
        zj = (z + y) >> 1;
        if (p[zj] <= L)
          z = zj;
        else
          y = zj;
      }
      if (p[y] <= L) z = y;
      ans++;
      swap(a[d], a[d - p[z] + 1]);
      b[a[d]] = d;
      b[a[d - p[z] + 1]] = d - p[z] + 1;
      w[ans][0] = d - p[z] + 1;
      w[ans][1] = d;
      d -= p[z] - 1;
      if (p[z] == L)
        L = 0;
      else
        L -= p[z] - 1;
    }
  }
  printf("%d\n", ans);
  for (int i = 1; i <= ans; i++) printf("%d %d\n", w[i][0], w[i][1]);
  return 0;
}
