#include <bits/stdc++.h>
using namespace std;
int data[100005], idx[100005], ans_c, ai[500005], aj[500005], x, id;
int arr[100005], i, j, k, n, m, Max, prime[100005];
bool notP[110005], isP;
int sum[200], add[200];
int abs(int p, int q) {
  if (p > q)
    return p - q;
  else
    return q - p;
}
void findP(int n) {
  m = 110000;
  notP[0] = notP[1] = 1;
  for (i = 2, k = 0;; i++) {
    if (notP[i]) {
      prime[i - 1] = prime[i - 2];
      continue;
    }
    arr[k++] = i;
    prime[i - 1] = i - 1;
    for (j = i; j < m; j += i) notP[j] = 1;
    if (i > n) break;
  }
}
int main() {
  scanf("%d", &n);
  findP(n);
  for (i = 1; i <= n; i++) {
    scanf("%d", &data[i]);
    idx[data[i]] = i;
  }
  for (i = 1; i < n; i++) {
    x = idx[i] - i;
    while (x) {
      id = idx[i];
      x -= prime[x];
      ai[ans_c] = i + x;
      aj[ans_c] = id;
      ans_c++;
      swap(data[i + x], data[id]);
      idx[i] = i + x;
      idx[data[id]] = id;
    }
  }
  printf("%d\n", ans_c);
  for (i = 0; i < ans_c; i++) printf("%d %d\n", ai[i], aj[i]);
}
