#include <bits/stdc++.h>
using namespace std;
int dirx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int diry[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int a[200006], b[200006], vis[200005] = {0};
vector<int> prime, ans1, ans2;
int main() {
  int n, fn, st, mid, r, k, t, sz, l;
  for (int i = 2; i < 800; i++) {
    if (vis[i] == 0) {
      for (int j = i * i; j < 200000; j += i) vis[j] = 1;
    }
  }
  for (int i = 2; i < 200000; i++)
    if (!vis[i]) prime.push_back(i);
  sz = prime.size();
  cin >> n;
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    a[i]--;
    b[a[i]] = i;
  }
  for (int i = 0; i < n; i++) {
    k = b[i];
    t = i;
    r = k - t;
    if (r == 0) continue;
    r++;
    while (1) {
      fn = sz - 1;
      st = 0;
      while (st + 1 != fn) {
        mid = (fn + st) / 2;
        if (prime[mid] > r)
          fn = mid;
        else
          st = mid;
      }
      ans1.push_back(k + 1);
      ans2.push_back(k + 2 - prime[st]);
      l = a[k + 1 - prime[st]];
      swap(a[k + 1 - prime[st]], a[k]);
      b[l] = k;
      b[i] = k + 1 - prime[st];
      if (prime[st] == r) break;
      k = k - prime[st] + 1;
      r = k - t + 1;
    }
  }
  cout << ans1.size() << endl;
  for (int i = 0; i < ans1.size(); i++) printf("%d %d\n", ans2[i], ans1[i]);
  return 0;
}
