#include <bits/stdc++.h>
using namespace std;
int a[100100], L[500100], R[500100], pos[100100], ps[9696], psc;
char p[100100];
int main() {
  int n;
  scanf("%d", &n);
  for (int i = (0); i < ((n)); ++i) scanf("%d", a + i);
  for (int i = (0); i < ((n)); ++i) --a[i];
  for (int i = (0); i < ((n)); ++i) pos[a[i]] = i;
  memset((p), (1), sizeof((p)));
  p[0] = p[1] = 0;
  for (int i = 2; i * i < 100100; ++i)
    if (p[i])
      for (int j = i * i; j < 100100; j += i) p[j] = 0;
  psc = 0;
  for (int i = (0); i < ((100100)); ++i)
    if (p[i]) ps[psc++] = i;
  int res = 0;
  for (int i = (0); i < ((n)); ++i)
    if (a[i] != i) {
      int j = pos[i];
      int d = j - i + 1;
      while (d > 1) {
        int k = (upper_bound(ps, ps + psc, d) - ps) - 1;
        int t = j - ps[k] + 1;
        L[res] = t;
        R[res] = j;
        ++res;
        pos[a[t]] = j;
        pos[a[j]] = t;
        swap(a[t], a[j]);
        j = pos[i];
        d = j - i + 1;
      }
    }
  printf("%d\n", res);
  for (int i = (0); i < ((res)); ++i) printf("%d %d\n", L[i] + 1, R[i] + 1);
  return 0;
}
