#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int a[MAXN], b[MAXN];
bool mark[MAXN];
vector<int> prime;
map<int, int> ind;
vector<pair<int, int> > answer;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ios::sync_with_stdio(0);
  cout.tie(0);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    b[i] = a[i];
  }
  sort(b, b + n);
  for (int i = 2; i <= n; i++) {
    if (mark[i] == false) {
      prime.push_back(-i);
    }
    for (int j = 2 * i; j <= n; j += i) {
      mark[j] = true;
    }
  }
  sort(prime.begin(), prime.end());
  for (int i = 0; i < n; i++) {
    ind[a[i]] = i;
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    if (a[i] == b[i]) {
      continue;
    }
    int cur = ind[b[i]];
    while (cur != i) {
      int prime_dis_index =
          lower_bound(prime.begin(), prime.end(), -(cur - i + 1)) -
          prime.begin();
      int dis_prime = prime[prime_dis_index];
      dis_prime = abs(dis_prime);
      dis_prime--;
      int now = cur - dis_prime;
      answer.push_back(make_pair(now, cur));
      ind[a[now]] = cur;
      ind[a[cur]] = now;
      swap(a[now], a[cur]);
      cur = now;
    }
  }
  cout << answer.size() << endl;
  for (int i = 0; i < answer.size(); i++) {
    cout << answer[i].first + 1 << ' ' << answer[i].second + 1 << endl;
  }
}
