#include <bits/stdc++.h>
using namespace std;
int prime[100500], cnt;
int a[100500];
int loc[100500];
int n, k;
int exch[100500 * 5][2];
void init() {
  bool flag[100500] = {0};
  cnt = 0;
  for (int i = 2; i < 100500; i++)
    if (!flag[i]) {
      prime[cnt++] = i;
      for (int j = i + i; j < 100500; j += i) flag[j] = true;
    }
}
int main() {
  init();
  while (scanf("%d", &n) == 1) {
    for (int i = 1; i <= n; i++) {
      scanf("%d", &a[i]);
      loc[a[i]] = i;
    }
    k = 0;
    for (int i = 1; i <= n; i++) {
      while (loc[i] > i) {
        int idx = lower_bound(prime, prime + cnt, loc[i] - i + 1) - prime;
        if (prime[idx] > loc[i] - i + 1) idx--;
        int x = loc[i] - prime[idx] + 1;
        exch[k][0] = x;
        exch[k++][1] = loc[i];
        loc[a[x]] = loc[i];
        swap(a[x], a[loc[i]]);
        loc[i] = x;
      }
    }
    cout << k << endl;
    for (int i = 0; i < k; i++) printf("%d %d\n", exch[i][0], exch[i][1]);
  }
}
