#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> p(n);
  for (int i = (0); i < ((n)); ++i) {
    cin >> x[i];
    --x[i];
    p[x[i]] = i;
  }
  int const MAX_SUM = 100001;
  vector<int> primes;
  for (int k = (2); k < (2 * n + 1); ++k) {
    bool isPrime = true;
    for (int j = 2; j * j <= k; ++j) {
      if (k % j == 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push_back(k);
    }
  }
  vector<pair<int, int> > res;
  for (int i = (0); i < ((n)); ++i) {
    int const pos1 = p[i];
    int const pos2 = i;
    int p1 = min(pos1, pos2);
    int const p2 = max(pos1, pos2);
    vector<int> positions;
    positions.push_back(p1);
    while (p1 != p2) {
      int const diff = p2 - p1 + 1;
      auto it = lower_bound(primes.begin(), primes.end(), diff);
      if (it == primes.end() || *it > diff) --it;
      int const usedPrime = *it;
      p1 += usedPrime - 1;
      positions.push_back(p1);
    }
    if (pos1 > pos2) reverse(positions.begin(), positions.end());
    for (int j = (0); j < (((int)positions.size() - 1)); ++j) {
      int const p1 = positions[j];
      int const p2 = positions[j + 1];
      swap(x[p1], x[p2]);
      p[x[p1]] = p1;
      p[x[p2]] = p2;
      res.push_back(make_pair(min(p1, p2), max(p1, p2)));
    }
  }
  vector<int> orig(n);
  for (int i = (0); i < ((n)); ++i) orig[i] = i;
  if (orig != x) {
    cout << "FAILED!\n";
    throw 10;
  }
  cout << (int)res.size() << endl;
  for (int i = (0); i < (((int)res.size())); ++i) {
    cout << res[i].first + 1 << " " << res[i].second + 1 << "\n";
  }
  return 0;
}
