#include <bits/stdc++.h>
using namespace std;
const int MaxLength = 500001;
typedef int arr[MaxLength];
typedef arr arr2[11];
typedef arr2 arr3[11];
int main() {
  int n;
  cin >> n;
  static arr a, ind, link;
  static pair<int, int> b[500002];
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
    b[i].first = a[i];
    b[i].second = i;
  }
  sort(b, b + n);
  for (int i = 0; i < n; i++) {
    ind[i] = b[i].second;
    link[ind[i]] = i;
  }
  static bool prime[500002];
  for (int i = 0; i <= MaxLength + 1; i++) prime[i] = true;
  prime[0] = prime[1] = false;
  for (int i = 2; i <= MaxLength; i++)
    if (prime[i])
      if (i * 1ll * i <= MaxLength)
        for (int j = i * i; j <= MaxLength; j += i) prime[j] = false;
  int res = 0;
  static pair<int, int> ans[600002];
  for (int i = 0; i < n; i++) {
    int ind1 = i, ind2 = ind[i];
    while (ind1 < ind2) {
      int j;
      for (j = ind1; j <= ind2; j++)
        if (prime[ind2 - j + 1] == true) break;
      ans[res].first = ind2, ans[res++].second = j;
      swap(ind[link[ind2]], ind[link[j]]);
      swap(link[ind2], link[j]);
      ind2 = j;
      if (ans[res - 1].first < ans[res - 1].second)
        swap(ans[res - 1].first, ans[res - 1].second);
    }
  }
  cout << res << endl;
  for (int i = 0; i < res; i++)
    printf("%d %d\n", ans[i].second + 1, ans[i].first + 1);
  return 0;
}
