#include <bits/stdc++.h>
using namespace std;
template <class T>
inline T gcd(T a, T b) {
  return b ? gcd(b, a % b) : a;
}
template <class T>
inline T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / gcd(a, b));
}
int prime[100032];
int loc[100032];
int o[100032];
vector<pair<int, int> > ans;
void swap(int &a, int &b) {
  int c = a;
  a = b;
  b = c;
}
int main() {
  memset(prime, 0, sizeof(prime));
  int lp = 0;
  for (int i = 2; i <= 100032; i++) {
    if (prime[i] == 0) {
      lp = i;
      lp--;
      prime[i] = lp;
      prime[lp] = lp;
      for (int j = i; j <= 100032; j += i) {
        prime[j] = lp;
      }
    } else {
      prime[i] = lp;
    }
  }
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &o[i]);
    loc[o[i]] = i;
  }
  int pos, npos;
  for (int i = 1; i <= n; i++) {
    while (loc[i] != i) {
      pos = loc[i];
      if (pos - i == 0) break;
      npos = pos - prime[pos - i];
      loc[o[npos]] = pos;
      swap(o[pos], o[npos]);
      loc[i] = npos;
      ans.push_back(make_pair(pos, npos));
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++)
    printf("%d %d\n", min(ans[i].first, ans[i].second),
           max(ans[i].first, ans[i].second));
  return 0;
}
