#include <bits/stdc++.h>
using namespace std;
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
int in[100005];
int prime_id[100005];
int num_prime;
vector<int> primes;
int ind[100005];
int N;
vector<pair<int, int> > ans2;
int solve(int dst, int src) {
  int ret = 0;
  if (dst == src) return 0;
  int p = src - dst + 1;
  while (prime_id[p] == 0) p--;
  while (dst != src) {
    ret++;
    int len = src - dst + 1;
    while (p > len) {
      p = primes[prime_id[p] - 1];
    }
    swap(in[src], in[src - (p - 1)]);
    swap(ind[in[src]], ind[in[src - (p - 1)]]);
    ans2.push_back(pair<int, int>(src, src - (p - 1)));
    src -= (p - 1);
  }
  return ret;
}
int main() {
  for (int i = 2; i * i < 100005; i++) {
    if (!prime_id[i]) {
      for (int j = i + i; j < 100005; j += i) {
        prime_id[j] = 1;
      }
    }
  }
  primes.push_back(0);
  for (int i = 2; i < 100005; i++) {
    if (!prime_id[i]) {
      num_prime++;
      primes.push_back(i);
      prime_id[i] = num_prime;
    } else {
      prime_id[i] = 0;
    }
  }
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    scanf("%d", &in[i + 1]);
    ind[in[i + 1]] = i + 1;
  }
  int ans = 0;
  for (int i = 1; i <= N; i++) {
    if (in[i] == i) continue;
    ans += solve(i, ind[i]);
  }
  printf("%d\n", ans);
  for (int i = 0; i < ans; i++)
    printf("%d %d\n", ans2[i].second, ans2[i].first);
  return 0;
}
