深搜。

#include <bits/stdc++.h>
using namespace std;
int n,ans;
int a[11];
bool vis[11];
bool prime(int x){
    for (int i=2;i*i<=x;i++){
        if (x%i==0){
            return 0;
        }
    }
    return 1;
}
void dfs(int i,int p,int c){//当前下标，前一个数，第一个数
    for (int j=1;j<=n;j++){
        if (!vis[j]&&(i==1||prime(j+p))){
            vis[j]=1;
            a[i]=j;
            if (i==n){
                if (prime(j+c)){//注意是环，最后一个数要和第一个数相加
                    ans++;
                    cout<<ans<<':';
                    for (int i=1;i<=n;i++){
                        cout<<a[i]<<' ';
                    }
                    cout<<endl;
                    vis[j]=0;//不要忘了在这里也要去标记
                    return;
                }
            }
            if (i==1){//记录第一个数
                c=j;
            }
            dfs(i+1,j,c);
            vis[j]=0;
        }
    }
}
int main(){
    cin>>n;
    dfs(1,0,0);
    cout<<"total:"<<ans;
    return 0;
}

另外吐槽一下，为什么很多题目都只有一个测试点

晕，只有一个测试点。