#include <bits/stdc++.h>
using namespace std;
double Fib(double x, double z);
string BinDec(unsigned long long x);
string StringInt(long long x);
unsigned long long StringInt(string x);
unsigned long long BinDec(string x);
unsigned long long POWMOD(unsigned long long x, unsigned long long y,
                          unsigned long long mod);
unsigned long long POWE(long long, long long);
long long fast_pow(long long a, long long b, long long mod) {
  if (b == 0) return 1ll;
  long long ans = 1;
  if (b % 2) return ans = (fast_pow(a, b - 1, mod) * a) % mod;
  ans = (fast_pow(a, b / 2, mod) % mod);
  return ((ans * ans) % mod);
}
int tree[100000 * 4] = {}, arr[100200] = {}, x;
void build(int in, int s, int e) {
  if (s == e) {
    tree[in] = s;
    return;
  }
  int m = (s + e) / 2;
  build(in * 2, s, m);
  build(in * 2 + 1, m + 1, e);
  if (arr[tree[in * 2]] > arr[tree[in * 2 + 1]])
    tree[in] = tree[in * 2 + 1];
  else
    tree[in] = tree[in * 2];
}
void up(int in, int s, int e, int ind, int v) {
  if (s > ind || ind > e) return;
  if (s == e && s == ind) {
    arr[s] = v;
    tree[in] = s;
    return;
  }
  int m = (s + e) / 2;
  up(in * 2, s, m, ind, v);
  up(in * 2 + 1, m + 1, e, ind, v);
  if (arr[tree[in * 2]] > arr[tree[in * 2 + 1]])
    tree[in] = tree[in * 2 + 1];
  else
    tree[in] = tree[in * 2];
}
long long qur(int in, int s, int e, int f, int l) {
  if (s > e || s > l || f > e) return 100001;
  if (f <= s && l >= e) return tree[in];
  int m = (s + e) / 2;
  long long v, i = qur(in * 2, s, m, f, l), j = qur(in * 2 + 1, m + 1, e, f, l);
  if (arr[i] > arr[j])
    v = j;
  else
    v = i;
  return v;
}
bool p[100210] = {};
int S = 0, SS = 0;
vector<int> v;
vector<pair<int, int> > ans;
pair<int, int> vv[100010] = {};
void sort() {
  int t;
  for (int i = 0; i < x; i++) {
    int j = qur(1, 0, x - 1, i, x - 1);
    if (i == j) continue;
    int k = j - i + 1;
    if (!p[k]) {
      ans.push_back({i, j});
      t = arr[i];
      up(1, 0, x - 1, i, arr[j]);
      up(1, 0, x - 1, j, t);
    } else if (k % 2 == 0) {
      if (p[j - i - vv[k].second + 1]) S++;
      ans.push_back({i + vv[k].second, j});
      t = arr[i + vv[k].second];
      up(1, 0, x - 1, i + vv[k].second, arr[j]);
      up(1, 0, x - 1, j, t);
      if (p[i + vv[k].second + -i - 1 + 1]) S++;
      ans.push_back({i + 1, i + vv[k].second});
      t = arr[i + 1];
      up(1, 0, x - 1, i + 1, arr[i + vv[k].second]);
      up(1, 0, x - 1, i + vv[k].second, t);
      if (p[i + 1 - i + 1]) S++;
      ans.push_back({i, i + 1});
      t = arr[i + 1];
      up(1, 0, x - 1, i + 1, arr[i]);
      up(1, 0, x - 1, i, t);
    } else {
      k++;
      i--;
      if (p[j - i - vv[k].second + 1]) S++;
      ans.push_back({i + vv[k].second, j});
      t = arr[i + vv[k].second];
      up(1, 0, x - 1, i + vv[k].second, arr[j]);
      up(1, 0, x - 1, j, t);
      if (p[i + vv[k].second + -i - 1 + 1]) SS++;
      ans.push_back({i + 1, i + vv[k].second});
      t = arr[i + 1];
      up(1, 0, x - 1, i + 1, arr[i + vv[k].second]);
      up(1, 0, x - 1, i + vv[k].second, t);
      i++;
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  for (long long i = 2; i <= 100000; i++) {
    if (!p[i]) {
      v.push_back(i);
      for (long long j = i * i; j <= 100000; j += i) p[j] = 1;
    }
  }
  for (int i = 4; i <= 100000; i += 2) {
    for (int j = 0; j < v.size(); j++) {
      if (!p[i - v[j]]) {
        vv[i] = {i - v[j], v[j]};
        break;
      }
    }
  }
  arr[100001] = 1e10;
  cin >> x;
  for (int i = 0; i < x; i++) cin >> arr[i];
  build(1, 0, x - 1);
  int j = 0;
  sort();
  if (S != 0 || SS != 0) cout << S << ' ' << SS << endl;
  cout << ans.size() << '\n';
  for (int i = 0; i < ans.size(); i++)
    cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << '\n';
  ;
  return 0;
}
