C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 352K, 提交时间: 2019-12-21 13:15:13

#include<bits/stdc++.h>
using namespace std;
int n,ts,vis[20],p[20];
int isprime(int x)
{
	for(int i=2;i*i<=x;i++)	if(x%i==0)	return 0;
	return 1;
}
void dfs(int x)
{
	if(x==n+1)
	{
		if(!isprime(p[n]+1))	return ;
		for(int i=1;i<=n;i++)
			if(i==n)	cout<<p[i]<<endl;
			else	cout<<p[i]<<' ';
		return ;
	}
	for(int i=2;i<=n;i++)
	{
		if(!vis[i]&&isprime(i+p[x-1]))
		{
			vis[i]=1;
			p[x]=i;
			dfs(x+1);
			vis[i]=0;
		}
	}
}
int main()
{
	p[1]=1,vis[1]=1;
	while(cin>>n)
	{
	//	if(ts)	cout<<endl;
		printf("Case %d:\n",++ts);
		dfs(2); puts("");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 348K, 提交时间: 2019-12-21 15:02:57

#include<bits/stdc++.h>
#define rep(i,s,e) for(int i=s; i<e; ++i)
using namespace std;
int n,cas,ans[25],vis[25];
int p[25]={0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0,0,1,0,1};
void dfs(int x){
	if(x>n&&p[ans[n]+1]) rep(i,1,n+1) 
		cout<<ans[i]<<(char)(i==n?'\n':' ');
	if(x<=n) rep(i,2,n+1) if(!vis[i]&&p[i+ans[x-1]]){
		vis[i]=1; ans[x]=i; dfs(x+1); vis[i]=0;
	}
}
void solve(){
	cout<<"Case "<<++cas<<":\n"; ans[1]=1;
	if(n%2==0) dfs(2); cout<<'\n';
}
int main(){
	while(cin>>n&&n) solve();
}