思路：从前往后想将1调整好，在调整2。。。。这样平均每次有五次机会调整，并且有相当一部分可能都用不到五次，能够一试。ac

代码：

#include<iostream>

#include<cstdio>

#include<cmath>

#include<map>

#include<queue>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=600005;

const int maxm=100005;

int P[maxm],p[maxm];

int u[maxn],v[maxn],da[maxn],pos[maxn];

void init()

{

    for(int i=2;i<maxm;i++)

        if(!P[i])

        for(int j=i*i;i<1000&&j<maxm;j+=i)

            P[j]=1;

}

int main()

{

    int n,cnt=0;

    init();

    for(int i=2;i<maxm;i++)

        if(!P[i])p[cnt++]=i;

    while(~scanf("%d",&n))

    {

        int scnt=0;

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

            scanf("%d",&da[i]),pos[da[i]]=i;

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

        {

            while(da[i]!=i)

            {

                int t=upper_bound(p,p+cnt,pos[i]-i+1)-p;

                t--;

                int tnp=pos[i],tmp=pos[i]-p[t]+1;

                int tm=da[tnp];

                da[tnp]=da[tmp];

                da[tmp]=tm;

                tm=pos[da[tnp]];

                pos[da[tnp]]=pos[da[tmp]];

                pos[da[tmp]]=tm;

                u[scnt]=tnp;v[scnt++]=tmp;

            }

        }

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

        for(int i=0;i<scnt;i++)

            printf("%d %d\n",v[i],u[i]);

    }

    return 0;

}