#include <bits/stdc++.h>
int prime[100010], cnt;
bool not_prime[100010] = {1, 1};
void db() {
  int i, j;
  memset(prime, 0, sizeof(prime));
  cnt = 0;
  for (i = 2; i < 100010; i++) {
    if (!not_prime[i]) prime[cnt++] = i;
    for (j = 0; j < cnt && i * prime[j] < 100010; j++) {
      not_prime[i * prime[j]] = 1;
      if ((i % prime[j]) == 0) break;
    }
  }
}
int abs(int n) {
  if (n >= 0) return n;
  return -1 * n;
}
int a[100100], b[500100][2], f[100010];
int main() {
  int i, j, k, s, n, p, t, q, m, x, y;
  db();
  for (i = 0; i < 100010; i++)
    if (not_prime[i] == 0) {
      not_prime[i - 1] = 0;
      not_prime[i] = 1;
    }
  for (i = 0; i < cnt; i++) prime[i] -= 1;
  while (scanf("%d", &n) != EOF) {
    for (i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      f[a[i]] = i;
    }
    q = s = 0;
    for (i = 1; i <= n; i++) {
      if (a[i] == i) continue;
      k = i - f[i];
      if (k < 0)
        p = -1;
      else
        p = 1;
      k = abs(k);
      while (k) {
        if (k == 1) {
          t = p;
          x = f[i];
          y = f[i] + t;
          if (p) {
            b[q][0] = y;
            b[q++][1] = x;
          } else {
            b[q][0] = x;
            b[q++][1] = y;
          }
          f[a[f[i] + t]] = x;
          f[i] = y;
          a[x] = a[y];
          a[y] = i;
          k -= 1;
          s += 1;
        } else if (k >= prime[cnt - 1]) {
          t = prime[cnt - 1] * p;
          x = f[i];
          y = f[i] + t;
          if (p) {
            b[q][0] = y;
            b[q++][1] = x;
          } else {
            b[q][0] = x;
            b[q++][1] = y;
          }
          f[a[f[i] + t]] = x;
          f[i] = y;
          a[x] = a[y];
          a[y] = i;
          s += 1;
          k -= prime[cnt - 1];
        } else {
          int st = 0;
          int en = cnt - 1;
          while (st <= en) {
            m = (st + en) / 2;
            if (prime[m] == k)
              break;
            else if (prime[m] < k && prime[m + 1] > k)
              break;
            else if (prime[m] > k)
              en = m - 1;
            else if (prime[m] < k)
              st = m + 1;
          }
          t = prime[m] * p;
          x = f[i];
          y = f[i] + t;
          if (p) {
            b[q][0] = y;
            b[q++][1] = x;
          } else {
            b[q][0] = x;
            b[q++][1] = y;
          }
          f[a[f[i] + t]] = x;
          f[i] = y;
          a[x] = a[y];
          a[y] = i;
          s += 1;
          k -= prime[m];
        }
      }
    }
    printf("%d\n", s);
    for (i = 0; i < q; i++) printf("%d %d\n", b[i][0], b[i][1]);
  }
}
