#include <bits/stdc++.h>
using namespace std;
int n, a[100000 + 1], pos[100000 + 1], p[100000 + 1], tot = 0, d[100000 + 1];
bool v[100000 + 1];
vector<pair<int, int> > ans;
inline void exchange(int x, int y) {
  if (x == y) return;
  swap(a[x], a[y]);
  swap(pos[a[x]], pos[a[y]]);
  ans.push_back(make_pair(x, y));
}
int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  for (int i = 2; i <= n; ++i) {
    if (!v[i]) p[tot++] = i;
    for (int j = 0; j < tot && i * p[j] <= n; ++j) {
      v[i * p[j]] = true;
      if (!(i % p[j])) break;
    }
  }
  for (int i = 4; i <= n + 1; i += 2)
    for (int j = 0; j < tot; ++j)
      if (!v[i - p[j]]) {
        d[i] = p[j];
        break;
      }
  for (int i = 1; i <= n; ++i) {
    if (a[i] == i) continue;
    int j = pos[i], len = j - i + 1;
    if (!v[len]) {
      exchange(i, j);
    } else if (len & 1) {
      exchange(j - d[len + 1] + 1, j);
      exchange(i, j - d[len + 1] + 1);
    } else {
      exchange(j - d[len] + 1, j);
      exchange(i + 1, j - d[len] + 1);
      exchange(i, i + 1);
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); ++i)
    cout << ans[i].first << " " << ans[i].second << endl;
  fclose(stdin);
  fclose(stdout);
  return 0;
}
