#include <bits/stdc++.h>
using namespace std;
pair<int, int> ans[100010 * 5];
int top;
int n, seq[100010], near[100010], pos[100010];
void read() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> seq[i];
    pos[seq[i]] = i;
  }
}
void Prepare(int n) {
  static int Prime[100010];
  static bool isPrime[100010];
  memset(isPrime, true, sizeof(isPrime));
  int m = 0;
  isPrime[1] = false;
  for (int i = 2; i <= n; ++i) {
    if (isPrime[i]) Prime[++m] = i;
    for (int j = 1; j <= m && Prime[j] * i <= n; ++j) {
      isPrime[Prime[j] * i] = false;
      if (i % Prime[j] == 0) break;
    }
  }
  for (int i = 2; i <= n; ++i) near[i] = isPrime[i] ? i : near[i - 1];
}
void Swap(int a, int b) {
  if (a > b) swap(a, b);
  for (int i = b - a + 1, x = b; i > 1;
       x = x - near[i] + 1, i = i - near[i] + 1) {
    ans[++top] = make_pair(x, x - near[i] + 1);
    swap(seq[x], seq[x - near[i] + 1]);
    swap(pos[seq[x]], pos[seq[x - near[i] + 1]]);
  }
}
void print() {
  for (int i = 1; i <= n; ++i)
    if (pos[i] != i) Swap(pos[i], i);
  printf("%d\n", top);
  for (int i = 1; i <= top; ++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);
  }
}
int main() {
  read();
  Prepare(n);
  print();
  return 0;
}
