#include <bits/stdc++.h>
using namespace std;
bool p[100010];
vector<int> pr;
vector<pair<int, int> > sol;
int n, pos[100010], v[100010], x, v1, v2, p1, p2;
void ciur() {
  int i = 2;
  while (i <= 316) {
    while (i < 100000 && p[i]) i++;
    for (int j = i * i; j < 100000; j += i) p[j] = 1;
    i++;
  }
  for (int i = 2; i < 100000; i++) {
    if (!p[i]) pr.push_back(i);
  }
}
int caut_bin(int x) {
  int l = 0, r = pr.size() - 1, md;
  while (r - l > 1) {
    md = (l + r) / 2;
    if (pr[md] <= x)
      l = md;
    else
      r = md;
  }
  return pr[r] <= x ? pr[r] : pr[l];
}
int main() {
  ciur();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &x);
    v[i] = x;
    pos[x] = i;
  }
  for (int i = 1; i <= n; i++) {
    while (pos[i] > i) {
      x = caut_bin(pos[i] - i + 1);
      p1 = pos[i] - x + 1;
      p2 = pos[i];
      sol.push_back(make_pair(p1, p2));
      v1 = v[p1];
      v2 = v[p2];
      v[p1] = v2;
      v[p2] = v1;
      pos[v1] = p2;
      pos[v2] = p1;
    }
  }
  printf("%d\n", sol.size());
  for (int i = 0; i < sol.size(); i++) {
    printf("%d %d\n", sol[i].first, sol[i].second);
  }
  return 0;
}
