#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:100000000000000")
using namespace std;
int n, arr[100011], pos[100011];
vector<int> p;
bool pri[100011];
string st;
vector<pair<int, int> > ans;
int bin(int x) {
  int ret = -1, l = 0, r = p.size();
  while (l < r) {
    int mid = (l + r) / 2;
    if (p[mid] > x)
      r = mid;
    else
      ret = mid, l = mid + 1;
  }
  return p[ret];
}
int main() {
  for (int i = 2; (i * i) < 100001; i++)
    if (pri[i] == 0)
      for (int j = i * 2; j < 100001; j += i) pri[j] = 1;
  for (int i = 2; i < 100001; i++)
    if (pri[i] == 0) p.push_back(i);
  cin >> n;
  for (int i = 0; i < n; i++) cin >> arr[i], pos[arr[i]] = i;
  for (int i = 0; i < n; i++)
    if (pos[i + 1] != i) {
      int ind = pos[i + 1];
      int dif = ind - i + 1;
      int x = bin(dif);
      if (x == dif) {
        ans.push_back(make_pair(i, ind));
        pos[arr[i]] = ind;
        swap(arr[i], arr[ind]);
      } else {
        x = i + x - 1;
        while (ind > x) {
          int ind2 = ind - x + 1;
          int x2 = bin(ind2);
          while ((ind - x2 + 1) >= x) {
            ans.push_back(make_pair((ind - x2 + 1), ind));
            pos[arr[(ind - x2 + 1)]] = ind;
            swap(arr[ind - x2 + 1], arr[ind]);
            ind = (ind - x2 + 1);
          }
        }
        ans.push_back(make_pair(i, ind));
        pos[arr[i]] = ind;
        swap(arr[i], arr[ind]);
      }
    }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++)
    cout << ans[i].first + 1 << ' ' << ans[i].second + 1 << endl;
  return 0;
}
