#include <bits/stdc++.h>
using namespace std;
long long mod = 998244353;
long long powerMod(long long a, long long n) {
  if (n == 0) return 1;
  long long res = powerMod((a % mod * a % mod) % mod, n / 2) % mod;
  if (n % 2) return (a % mod * res % mod) % mod;
  return res;
}
bool prime[1111111];
void initialize() {
  prime[0] = prime[1] = true;
  for (long long i = 2; i * i <= 100000; i++)
    for (long long j = i * 2; j <= 100000; j += i) prime[j] = 1;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  initialize();
  long long n;
  cin >> n;
  long long a[n + 1];
  long long pos[n + 1];
  for (long long i = 1; i < n + 1; i++) cin >> a[i], pos[a[i]] = i;
  vector<pair<long long, long long> > ans;
  for (long long i = 1; i < n + 1; i++) {
    long long ct = 0;
    while (a[i] != i) {
      ct++;
      long long temp = pos[i] - i + 1;
      long long j = temp;
      while (prime[j]) j--;
      ans.push_back({pos[i] - j + 1, pos[i]});
      long long first = a[pos[i] - j + 1];
      long long second = a[pos[i]];
      long long x1 = pos[i] - j + 1;
      long long y1 = pos[i];
      pos[second] = x1;
      pos[first] = y1;
      a[x1] = second;
      a[y1] = first;
    }
  }
  cout << ans.size() << '\n';
  for (auto it : ans) cout << it.first << ' ' << it.second << '\n';
  return 0;
}
