原贴：https://www.luogu.com.cn/discuss/show/280692

更新后代码:

#include<bits/stdc++.h>
using namespace std;
int n,a[1001],vis[1001];
bool prime(int n)
{
	if(n==2)
	{
		return 1;
	}
	if(n&1==0)
	{
		return 0;
	}
	if(n==2||n==3||n==5||n==7||n==11||n==13||n==17||n==19||n==23||n==29||n==31||n==37)
	{
		return 1;
	}
	return 0;
}
void print()
{
	bool flag=1;
	for(int i=1;i<n;i++)
	{
		if(!prime(a[i]+a[i+1]))
		{
			flag=0;
			return;
		}
	}
	if(!prime(a[n]+a[1])||a[1]!=1)
	{
		flag=0;
		return;
	}
	if(flag)
	{
		for(int i=1;i<=n;i++)
		{
			cout<<a[i]<<" ";
		}
		cout<<"\n";
	}
	//memset(a,0,sizeof(a));
	return;
}
void dfs(int dep)
{
	if(dep==n+1)
	{
		print();
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(!vis[i])
		{
			vis[i]=1;
			a[dep]=i;
			dfs(dep+1);
			vis[i]=0;
		}
	}
}
int main()
{
	int i=1;
	while(scanf("%d",&n)!=EOF)
	{
		memset(a,0,sizeof(a));
		memset(vis,0,sizeof(vis));
		printf("Case %d:\n",i);
		dfs(1);
		
		printf("\n");
		i++;
	}
}

已经从O(n*n!*sqrt(n))优化到O(n*n!)了还不优吗，还是不对啊,这题长得太毒瘤了