#include <bits/stdc++.h>
using namespace std;
int n, a[100009], pos[100009];
vector<pair<int, int> > ans;
bitset<100009> num;
int main() {
  vector<int> p;
  for (int i = 2; i * i < 100009; ++i)
    if (!num[i])
      for (long long j = i * 1LL * i; j < 100009; j += i) num[j] = 1;
  for (int i = 2; i < 100009; ++i)
    if (!num[i]) p.push_back(i);
  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) {
    while (pos[i] != i) {
      int len = pos[i] - i + 1;
      int idx = upper_bound(p.begin(), p.end(), len) - p.begin();
      --idx;
      int v = p[idx];
      int x = pos[i];
      int y = pos[i] - v + 1;
      swap(a[x], a[y]);
      pos[a[x]] = x;
      pos[a[y]] = y;
      ans.push_back({y, x});
    }
  }
  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;
}
