#include <bits/stdc++.h>
using namespace std;
const int lim = 100000;
int inp[lim + 4], sz = 1;
bool vis[lim + 4] = {false};
int pos[lim + 4];
vector<int> prime;
vector<pair<int, int> > p;
void makeprime(int n) {
  for (int i = 3; i <= n; i += 2) {
    int x = i * 2;
    while (x <= n) vis[x] = true, x += i;
  }
  prime.push_back(2);
  for (int i = 3; i <= n; i += 2)
    if (!vis[i] && i % 2 != 0) prime.push_back(i), sz++;
}
int bs(int i, int j, int val) {
  if (i == j || prime[i] == val)
    if (prime[i] > val)
      return prime[i - 1];
    else
      return prime[i];
  int mid = (i + j) / 2;
  if (prime[mid] == val) return prime[mid];
  if (prime[mid] < val) return bs(mid + 1, j, val);
  return bs(i, mid, val);
}
void swa(int i, int j) {
  pos[inp[i]] = j;
  pos[inp[j]] = i;
  int x = inp[i];
  inp[i] = inp[j];
  inp[j] = x;
  p.push_back(make_pair(j, i));
}
int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> inp[i], pos[inp[i]] = i;
  makeprime(n);
  int i = 1;
  while (i <= n) {
    if (i == inp[i]) {
      i++;
      continue;
    }
    int cha = 0;
    cha = bs(0, sz - 1, pos[i] - i + 1);
    swa(pos[i], pos[i] - (cha - 1));
  }
  cout << p.size() << endl;
  for (int i = 0; i < p.size(); i++)
    cout << p[i].first << " " << p[i].second << endl;
}
