#include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <cmath>

 #define maxn 100010

 using namespace std;

 int n;

 int a[maxn+];

 bool vis[maxn+];

 int f[maxn+];

 int p[maxn];

 int s[maxn*],e[maxn*];

 int cnt=;

 int bs(int x,int l,int r)

 {

     int pos=;

     while(l<r)

     {

         int mid=(l+r)/;

         if(f[mid]>x)

         {

             r=mid;

         }

         else

         {

             l=mid+;

             pos=l;

         }

     }

     return pos;

 }

 void get_prime()

 {

     vis[]=true;

     vis[]=true;

     for(int i=; i<maxn; i++)

     {

         if(!vis[i])

         {

             for(int j=i*; j<maxn; j+=i)

             {

                 vis[j]=true;

             }

         }

     }

     for(int i=; i<maxn; i++)

     {

         if(!vis[i])

         {

            f[cnt++]=i;

         }

     }

 }

 int main()

 {

     get_prime();

     scanf("%d",&n);

     for(int i=; i<=n; i++)

     {

         scanf("%d",&a[i]);

         p[a[i]]=i;

     }

     int ans=;

     for(int i=; i<=n; i++)

     {

         while(a[i]!=i)

         {

            int t=bs(p[i]-i+,,cnt-);

            t--;

            int sx=p[i],ex=p[i]-f[t]+;

            swap(a[sx],a[ex]);

            swap(p[a[sx]],p[a[ex]]);

            s[ans]=sx; e[ans++]=ex;

         }

     }

     printf("%d\n",ans);

     for(int i=; i<ans; i++)

     {

         printf("%d %d\n",e[i],s[i]);

     }

     return ;

 }