#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> > ans;
int a[100005];
int pos[100005];
bool nonpr[1230997];
int prime[1230997];
int nPrime;
vector<int> prime_list;
void eratos(int n) {
  int i, j;
  nonpr[0] = nonpr[1] = true;
  for (i = 2; i <= n; i++)
    if (!nonpr[i])
      for (j = i + i; j <= n; j += i) nonpr[j] = true;
  for (i = 1; i <= n; i++)
    if (!nonpr[i]) prime_list.push_back(i);
}
int findPrime(int x) {
  vector<int>::iterator it =
      lower_bound(prime_list.begin(), prime_list.end(), x);
  if (*it == x) return x;
  return prime_list[it - prime_list.begin() - 1];
}
int main() {
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    pos[a[i]] = i;
  }
  eratos(1230990);
  for (int i = n; i >= 1; i--) {
    int p = pos[i];
    while (p < i) {
      int ap = p + findPrime(i - p + 1) - 1;
      pos[a[ap]] = p;
      swap(a[p], a[ap]);
      ans.push_back(pair<int, int>(p, ap));
      p = ap;
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
}
