#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, y;
};
vector<node> answer;
int dis[1000005], a[1000005], pre[1000005];
bool prime[1000005];
void getprime() {
  for (int i = 2; i < 1000005 - 5; i++) {
    if (!prime[i]) {
      for (int j = i * 2; j < 1000005 - 5; j += i) {
        prime[j] = true;
      }
    }
  }
  int maxx = 2;
  for (int i = 2; i < 1000005 - 5; i++) {
    if (prime[i] == false) maxx = i;
    pre[i] = maxx;
  }
}
int main() {
  getprime();
  int n;
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    dis[a[i]] = i;
  }
  int t = 0;
  for (int i = 1; i <= n; i++) {
    if (a[i] == i) continue;
    int j = dis[i];
    while (j != i) {
      int k = pre[j - i + 1];
      k = j - k + 1;
      node q;
      q.x = k, q.y = j;
      answer.push_back(q);
      swap(dis[a[j]], dis[a[k]]);
      swap(a[j], a[k]);
      j = k;
    }
  }
  printf("%d\n", answer.size());
  for (int i = 0; i < answer.size(); i++) {
    printf("%d %d\n", answer[i].x, answer[i].y);
  }
}
