#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int pos[100005], a[100005];
int main() {
  int n, t, m, l, k, ans, i, j, res = 0, fl;
  t = 1;
  while (t--) {
    int isprime[100005];
    for (i = 2; i <= 100004; ++i) isprime[i] = 1;
    isprime[0] = isprime[1] = 0;
    for (i = 2; i <= sqrt(100005); ++i) {
      if (!isprime[i]) continue;
      for (j = i * i; j < 100005; j += i) isprime[j] = 0;
    }
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
      scanf("%d", &a[i]);
      pos[a[i]] = i + 1;
    }
    vector<pair<int, int> > res;
    int j = n;
    int i;
    for (i = 1; i <= n; i++) {
      int j = pos[i];
      if (i == j) continue;
      k = i;
      while (pos[i] != i) {
        j = pos[i];
        k = i;
        while (!isprime[j - k + 1]) k++;
        res.push_back(make_pair(k, j));
        int temp = pos[i];
        pos[i] = k;
        pos[a[k - 1]] = j;
        temp = a[j - 1];
        a[j - 1] = a[k - 1];
        a[k - 1] = temp;
      }
    }
    printf("%d ", res.size());
    puts("");
    for (i = 0; i < res.size(); i++) {
      printf("%d ", res[i].first);
      printf("%d ", res[i].second);
      puts("");
    }
  }
  return 0;
}
