#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n;
int pos[100005], A[100005];
bool Prime[100005];
vector<pair<int, int>> ans;
void sieve() {
  memset(Prime, true, sizeof Prime);
  Prime[0] = Prime[1] = false;
  for (int p = 2; p * p <= 100001; p++) {
    if (Prime[p] == true) {
      for (int i = p * 2; i <= 100001; i += p) Prime[i] = false;
    }
  }
}
void PutInPosition(int c) {
  if (pos[c] == c) return;
  int i = c;
  while (!Prime[pos[c] - i + 1]) i++;
  ans.push_back({i, pos[c]});
  swap(A[i], A[pos[c]]);
  swap(pos[A[pos[c]]], pos[c]);
  PutInPosition(c);
}
int main() {
  sieve();
  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++) PutInPosition(i);
  printf("%d\n", ans.size());
  for (int i = 0; i < ans.size(); i++)
    printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}
