#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
long long max3(long long x, long long y, long long z) {
  return max(max(x, y), z);
}
long long min3(long long x, long long y, long long z) {
  return min(min(x, y), z);
}
const long long M = 2e5 + 10, M2 = 1e6 + 10, mod = 1e9 + 7, inf = 1e17 + 10;
void add(int& a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}
int X[] = {0, 1, 0, -1};
int Y[] = {-1, 0, 1, 0};
long long power(long long x, long long n) {
  long long result = 1;
  while (n > 0) {
    if (n % 2 == 1) result = (result * x) % mod;
    x = ((x % mod) * (x % mod)) % mod;
    n = n / 2;
  }
  return result;
}
long long n;
long long number[100001];
long long position[100001];
long long prime[100001];
vector<long long> pr;
vector<pair<long long, long long> > v;
long long moves = 0;
void sieve() {
  prime[0] = 0;
  prime[1] = 0;
  for (long long i = 2; i <= 100000; i++) {
    if (prime[i]) {
      pr.push_back(i);
      for (long long j = i * i; j <= 100000; j += i) {
        prime[j] = 0;
      }
    }
  }
}
void swapIndex(long long i, long long j) {
  long long firstnum = number[i];
  long long secondnum = number[j];
  moves++;
  v.push_back({i, j});
  position[firstnum] = j;
  position[secondnum] = i;
  number[i] = secondnum;
  number[j] = firstnum;
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  memset(prime, 1, sizeof(prime));
  sieve();
  cin >> n;
  for (long long i = 1; i < n + 1; i++) {
    long long x;
    cin >> x;
    number[i] = x;
    position[x] = i;
  }
  for (long long i = n; i >= 1; i--) {
    while (position[i] != i) {
      long long j = i - position[i] + 1;
      auto it = --lower_bound(pr.begin(), pr.end(), j + 1);
      swapIndex(position[i], position[i] + *it - 1);
    }
  }
  cout << moves << "\n";
  for (auto u : v) {
    cout << u.first << " " << u.second << "\n";
  }
  return 0;
}
