#include <bits/stdc++.h>
using namespace std;
const int SIZE = 200000;
int p[200000], pcnt;
int ans[5 * SIZE][2];
int T[SIZE], v[SIZE];
int answer;
int a[SIZE], b[SIZE];
void isPrime(int n) {
  for (int i = 0; i < pcnt; i++)
    if (n % p[i] == 0) return;
  p[pcnt++] = n;
}
void make_swap(int i, int j) {
  if (i < j) swap(i, j);
  ans[answer][0] = j;
  ans[answer][1] = i;
  answer++;
  swap(v[i], v[j]);
  T[v[i]] = i;
  T[v[j]] = j;
}
void calc(int value) {
  int i = value;
  int j = T[value];
  int s = j - i + 1;
  if (s == 1) return;
  if (s <= 3) {
    make_swap(j, i);
    return;
  }
  if (s % 2 == 0) {
    make_swap(j, j - 1);
    if (s == 2) return;
    s--;
    j--;
  }
  if (s <= 3) {
    make_swap(j, i);
    return;
  }
  make_swap(j, j - p[b[s + 1]] + 1);
  make_swap(j - p[b[s + 1]] + 1, i);
}
int main() {
  int N, i, j, s;
  scanf("%d", &N);
  for (i = 1; i <= N; i++) {
    scanf("%d", &v[i]);
    T[v[i]] = i;
  }
  p[pcnt++] = 2;
  for (i = 3; i <= N; i += 2) isPrime(i);
  for (i = 0; i <= N; i++) a[i] = -1;
  for (i = 0; i < pcnt; i++)
    for (j = i; j < pcnt; j++) {
      s = p[i] + p[j];
      if (s > N + 10) break;
      a[s] = i;
      b[s] = j;
    }
  for (i = 1; i <= N; i++) {
    calc(i);
  }
  printf("%d\n", answer);
  for (i = 0; i < answer; i++) printf("%d %d\n", ans[i][0], ans[i][1]);
  return 0;
}
