#include <bits/stdc++.h>
using namespace std;
int s[100030], prime[100030], res = 0, pathx[100030 * 5], pathy[100030 * 5];
void getprime() {
  memset(prime, 0, sizeof(prime));
  prime[0] = 1;
  prime[1] = 1;
  for (int i = 2; i < 100030; i++) {
    if (prime[i] == 0) {
      for (int j = i * 2; j < 100030; j += i) prime[j] = 1;
    }
  }
}
void change(int x, int y) {
  if (x == y)
    return;
  else if (x < y)
    swap(x, y);
  for (int i = x; i > y; i--) {
    if (prime[i - y + 1] == 0) {
      pathx[res] = y;
      pathy[res] = i;
      swap(s[y], s[i]);
      y = i;
      res++;
      change(x, y);
      break;
    }
  }
}
int main() {
  int n;
  getprime();
  while (scanf("%d", &n) != EOF) {
    res = 0;
    for (int i = 1; i <= n; i++) {
      scanf("%d", &s[i]);
    }
    for (int i = 1; i <= n; i++) {
      while (s[i] != i) change(s[i], i);
    }
    printf("%d\n", res);
    for (int i = 0; i < res; i++) {
      printf("%d %d\n", pathx[i], pathy[i]);
    }
  }
}
