#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  vector<int> pos(n);
  for (int i = 0; i < n; ++i) {
    cin >> v[i];
    --v[i];
    pos[v[i]] = i;
  }
  vector<bool> pr(111111, true);
  vector<int> primes;
  pr[0] = false;
  pr[1] = false;
  for (int i = 2; i < 111111; ++i) {
    if (!pr[i]) continue;
    primes.push_back(i);
    int k = 2;
    while (k * i < 111111) {
      pr[k * i] = false;
      ++k;
    }
  }
  vector<pair<int, int> > ans;
  for (int i = 0; i < n; ++i) {
    while (pos[i] != i) {
      int dist = max(pos[i] - i, i - pos[i]) + 1;
      int prime = *(upper_bound(primes.begin(), primes.end(), dist) - 1);
      if (i > pos[i]) {
        int t = pos[i];
        swap(v[t], v[t + prime - 1]);
        pos[v[t]] = t;
        pos[v[t + prime - 1]] = t + prime - 1;
        ans.push_back(make_pair(t, t + prime - 1));
      } else {
        int t = pos[i];
        swap(v[t], v[t - prime + 1]);
        pos[v[t]] = t;
        pos[v[t - prime + 1]] = t - prime + 1;
        ans.push_back(make_pair(t, t - prime + 1));
      }
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); ++i) {
    if (ans[i].first > ans[i].second) swap(ans[i].first, ans[i].second);
    cout << ans[i].first + 1 << " " << ans[i].second + 1 << endl;
  }
}
