#include <bits/stdc++.h>
using namespace std;
bool is_prime[100005];
int a[100005], pos[100005];
vector<pair<int, int> > ans;
void init() {
  memset(is_prime, true, sizeof(is_prime));
  is_prime[1] = false;
  for (int i = 2; i < 1000; i++) {
    if (is_prime[i]) {
      for (int j = i * i; j < 100002; j += i) {
        is_prime[j] = false;
      }
    }
  }
  return;
}
int main(void) {
  init();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", a + i);
    pos[a[i]] = i;
  }
  for (int i = 1; i <= n; i++) {
    if (i == a[i]) continue;
    if (is_prime[pos[i] - i + 1]) {
      swap(a[i], a[pos[i]]);
      ans.push_back(pair<int, int>(pos[i], i));
      pos[a[pos[i]]] = pos[i];
      pos[i] = i;
    } else {
      int d = pos[i] - i;
      while (d) {
        for (int k = d; k >= 1; k--) {
          if (is_prime[k + 1]) {
            swap(a[i + d - k], a[pos[i]]);
            ans.push_back(pair<int, int>(i + d - k, pos[i]));
            pos[a[pos[i]]] = pos[i];
            pos[i] = i + d - k;
            d -= k;
            break;
          }
        }
      }
    }
  }
  int len = ans.size();
  printf("%d\n", len);
  for (int i = 0; i < len; i++) {
    if (ans[i].first > ans[i].second) {
      swap(ans[i].first, ans[i].second);
    }
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
  return 0;
}
