#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
using namespace std;
const long long maxn = 1e6 + 100, inf = 1e18, LOG = 23, mod = 998244353;
int block = 300, timer = 0;
const long double EPS = 1e-7;
vector<int> prime;
int dist[maxn], n, m, w[maxn], a[maxn], p[maxn];
vector<pair<int, int> > que, res;
int main() {
  n = 1e5;
  prime.push_back(2);
  m = sqrt(n) + 10;
  for (int i = 3; i <= m; i += 2) {
    if (w[i]) continue;
    w[i] = 1;
    prime.push_back(i);
    for (int j = i * i; j <= n; j += i + i) {
      w[j] = 1;
    }
  }
  for (int i = m + 1 + m % 2; i <= n; i += 2) {
    if (w[i] == 0) prime.push_back(i);
  }
  prime.push_back(1e5 + 2);
  for (int i = 0; i < prime.size() - 1; ++i) {
    dist[prime[i] - 1] = prime[i];
    for (int j = prime[i]; j <= prime[i + 1] - 2; ++j) {
      dist[j] = dist[j - prime[i] + 1];
    }
  }
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    p[a[i]] = i;
  }
  for (int i = 1; i <= n; ++i) {
    int cur = p[i] - i;
    int pos = p[i];
    while (cur != 0) {
      if (cur < 0) {
        que.push_back({pos, pos + dist[-cur] - 1});
        pos += dist[-cur] - 1;
        cur = pos - i;
      } else {
        que.push_back({pos, pos - dist[cur] + 1});
        pos -= dist[cur] - 1;
        cur = pos - i;
      }
    }
    int sz = que.size();
    a[p[i]] = a[i];
    p[a[i]] = p[i];
    a[i] = i;
    p[i] = i;
    for (int j = sz - 2; j >= 0; j--) {
      que.push_back(que[j]);
    }
    for (auto j : que) {
      res.push_back(j);
    }
    que.clear();
  }
  cout << res.size() << endl;
  for (auto i : res) {
    if (i.first > i.second) swap(i.first, i.second);
    cout << i.first << " " << i.second << endl;
  }
}
