#include <bits/stdc++.h>
using namespace std;
int a[200000], c[5000], b[1000], f[5000], r[5000][10], w[200000], g[500010][2],
    p[200000], q[200000];
int tp, tot;
void dog() {
  int i, j, t1, _max, t2;
  for (i = 1; i <= 100000; i++) a[i] = 0;
  a[1] = 1;
  for (i = 2; i <= 100000; i++)
    if (a[i] == 0) {
      for (j = 2; j <= 100000 / i; j++) a[i * j] = 1;
    }
  tp = 0;
  for (i = 1; i <= 100; i++)
    if (a[i] == 0) b[++tp] = i - 1;
  t1 = 1;
  _max = 0;
  t2 = 0;
  for (i = 1; i <= 100000; i++)
    if (a[i] == 0) {
      t1 = i;
      w[i] = i;
    } else {
      w[i] = t1;
    }
}
void swap(int &x, int &y) {
  int t;
  t = x;
  x = y;
  y = t;
}
void pig(int index, int x) {
  int p1, x1, xt, t1, i;
  if (index == x + 1) {
    swap(q[index], q[x]);
    p[q[x]] = x;
    p[q[index]] = index;
    g[++tot][0] = x;
    g[tot][1] = index;
    return;
  }
  p1 = index - x;
  x1 = p1 - w[p1] + 1;
  xt = x;
  for (i = 1; i <= r[x1][0]; i++) {
    t1 = r[x1][i];
    swap(q[xt], q[xt + t1]);
    p[q[xt]] = xt;
    p[q[xt + t1]] = xt + t1;
    g[++tot][0] = xt;
    g[tot][1] = xt + t1;
    xt = xt + t1;
  }
  swap(q[xt], q[index]);
  p[q[xt]] = xt;
  p[q[index]] = index;
  g[++tot][0] = xt;
  g[tot][1] = index;
}
int main() {
  int i, j, index, t1, n;
  dog();
  for (i = 1; i <= 200; i++) c[i] = 10000;
  c[0] = 0;
  for (i = 1; i <= tp; i++)
    for (j = 200 - b[i]; j >= 0; j--)
      if (c[j] + 1 < c[j + b[i]]) {
        c[j + b[i]] = c[j] + 1;
        f[j + b[i]] = b[i];
      }
  for (i = 1; i <= 200; i++) {
    index = i;
    t1 = 0;
    while (index) {
      r[i][++t1] = f[index];
      index = index - f[index];
    }
    r[i][0] = t1;
  }
  scanf("%d", &n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &q[i]);
    p[q[i]] = i;
  }
  tot = 0;
  for (i = n; i >= 1; i--) {
    if (p[i] == i) continue;
    pig(i, p[i]);
  }
  printf("%d\n", tot);
  for (i = 1; i <= tot; i++) printf("%d %d\n", g[i][0], g[i][1]);
  return 0;
}
