#include <bits/stdc++.h>
using namespace std;
template <class T1>
void deb(T1 e1) {
  cout << e1 << endl;
}
template <class T1, class T2>
void deb(T1 e1, T2 e2) {
  cout << e1 << " " << e2 << endl;
}
template <class T1, class T2, class T3>
void deb(T1 e1, T2 e2, T3 e3) {
  cout << e1 << " " << e2 << " " << e3 << endl;
}
template <class T1, class T2, class T3, class T4>
void deb(T1 e1, T2 e2, T3 e3, T4 e4) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << endl;
}
template <class T1, class T2, class T3, class T4, class T5>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << endl;
}
template <class T1, class T2, class T3, class T4, class T5, class T6>
void deb(T1 e1, T2 e2, T3 e3, T4 e4, T5 e5, T6 e6) {
  cout << e1 << " " << e2 << " " << e3 << " " << e4 << " " << e5 << " " << e6
       << endl;
}
int n, arr[100005 + 7], pos[100005 + 7], sz, f;
bool visit[100005 + 7];
vector<int> prime;
vector<pair<int, int> > ans;
void reset();
void cal_prime();
void swap_two(int i, int j);
void b_search(int left, int right, int v);
int main() {
  int cnt, d, p, res, i, j, k;
  cal_prime();
  while (scanf("%d", &n) == 1) {
    reset();
    for (i = 1; i <= n; i++) {
      scanf("%d", &arr[i]);
      pos[arr[i]] = i;
    }
    for (i = 1; i <= n; i++) {
      if (arr[i] == i) {
        continue;
      }
      p = pos[i];
      d = p - i + 1;
      while (d > 1) {
        b_search(0, sz, d);
        f = p - f + 1;
        pos[arr[p]] = f;
        pos[arr[f]] = p;
        swap(arr[p], arr[f]);
        ans.push_back(pair<int, int>(f, p));
        p = f;
        d = p - i + 1;
      }
    }
    res = ans.size();
    printf("%d\n", res);
    for (i = 0; i < res; i++) {
      printf("%d %d\n", ans[i].first, ans[i].second);
    }
  }
  return 0;
}
void reset() { ans.clear(); }
void cal_prime() {
  long long int i, j, k;
  memset((visit), 0, sizeof(visit));
  prime.push_back(2);
  for (i = 3; i <= 100005; i += 2) {
    if (!visit[i]) {
      prime.push_back(i);
      for (j = i * i; j <= 100005; j += i) {
        visit[j] = 1;
      }
    }
  }
  sz = prime.size();
  sz--;
}
void b_search(int left, int right, int v) {
  if (left > right) {
    return;
  }
  int mid;
  mid = (left + right) / 2;
  if (prime[mid] <= v) {
    f = prime[mid];
    b_search(mid + 1, right, v);
  } else {
    b_search(left, mid - 1, v);
  }
}
