#include <bits/stdc++.h>
using namespace std;
set<int> s;
void fn(int n) {
  bool prime[n + 1];
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * 2; i <= n; i += p) prime[i] = false;
    }
  }
  for (int p = 2; p <= n; p++)
    if (prime[p]) s.insert(p);
}
int main() {
  int n;
  cin >> n;
  int a[n + 1];
  fn(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int i = 1;
  vector<pair<int, int> > ans;
  while (i <= n) {
    if (i == a[i]) {
      ++i;
      continue;
    }
    int j = i;
    while (j >= 1 && j <= n && j != a[j]) {
      int temp = abs(a[j] - j + 1);
      set<int>::iterator it = s.upper_bound(temp);
      int pos = 2;
      if (it != s.begin()) {
        --it;
        pos = *it;
      }
      int temp1 = (a[j] < j) ? j - pos + 1 : j + pos - 1;
      ans.push_back(make_pair(j, temp1));
      swap(a[j], a[temp1]);
      j = temp1;
    }
  }
  int si = ans.size();
  cout << si << "\n";
  for (int i = 0; i < si; i++) {
    cout << ans[i].first << " " << ans[i].second << "\n";
  }
}
