#include <bits/stdc++.h>
using namespace std;
int n, ans, a[1000005], pos[1000005], pr[1000005];
vector<pair<int, int> > cvp;
int isprime(int num) {
  if (!pr[num]) return 1;
  return 0;
}
void degis(int i, int j) {
  int x = a[i], y = a[j];
  a[j] = x;
  pos[x] = j;
  a[i] = y;
  pos[y] = i;
  cvp.push_back(make_pair(i, j));
}
int asalbul(int num) {
  while (num > 1) {
    if (isprime(num)) return num;
    num--;
  }
  return 2;
}
void yap(int ind) {
  if (ind == a[ind]) return;
  int ps = pos[ind];
  int p = asalbul(ps - ind + 1);
  degis(ps, ps - p + 1);
  if (ind != a[ind]) yap(ind);
}
void asal() {
  for (int i = 2; i <= 100000; i++) {
    if (pr[i]) continue;
    for (int j = 2 * i; j <= 100000; j += i) pr[j] = 1;
  }
}
int main() {
  asal();
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (i != a[i]) yap(i);
  }
  cout << cvp.size() << '\n';
  for (__typeof(cvp.begin()) k = cvp.begin(); k != cvp.end(); k++)
    cout << k->second << " " << k->first << '\n';
  return 0;
}
