#include <bits/stdc++.h>
using namespace std;
template <class T>
T gcd(T a, T b) {
  T r;
  while (b != 0) {
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}
template <class T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <class T>
int getbit(T s, int i) {
  return (s >> i) & 1;
}
template <class T>
T onbit(T s, int i) {
  return s | (T(1) << i);
}
template <class T>
T offbit(T s, int i) {
  return s & (~(T(1) << i));
}
const double PI = 2 * acos(0.0);
const double eps = 1e-9;
const int infi = (1 << 31) - 1;
const long long Linfi = (long long)1e18;
const int MOD = 1000000007;
int n, cnt = 0;
int a[110005], p[110005], u[110005], vitri[110005];
vector<pair<int, int> > ans;
void sang(int n) {
  memset(p, 0, sizeof(p));
  for (int i = 2; i <= sqrt(n); i++) {
    if (p[i] == 0) {
      for (int j = i * i; j <= n; j += i) p[j] = 1;
    }
  }
  for (int i = 2; i <= n; i++)
    if (p[i] == 0) u[++cnt] = i - 1;
}
void solve() {
  for (int i = 1; i <= n; i++) {
    int pos = vitri[i];
    if (pos == i) continue;
    int delta = pos - i;
    int tmp = lower_bound(u + 1, u + cnt + 1, delta) - u;
    if (u[tmp] > delta) tmp--;
    int x = u[tmp];
    int k = pos - x;
    swap(a[k], a[pos]);
    ans.push_back(make_pair(k, pos));
    swap(vitri[a[k]], vitri[a[pos]]);
    while (k > i) {
      while (u[tmp] > k - i) tmp--;
      x = u[tmp];
      if (x == 0) break;
      swap(a[k], a[k - x]);
      ans.push_back(make_pair(k - x, k));
      swap(vitri[a[k]], vitri[a[k - x]]);
      k -= x;
      if (k == i) break;
      if (ans.size() >= 500000) return;
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) {
    printf("%d %d\n", ans[i].first, ans[i].second);
  }
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    vitri[a[i]] = i;
  }
  sang(110001);
  solve();
  return 0;
}
