素数环(dfs)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[25];
ll f[25];//判断是否用过

bool isprime(ll n)
{
	if(n==1)
		return false;
	else 
		for(ll i=2;i<=n/i;i++)
			if(n%i==0)
				return false;
	return true;
}

void dfs(ll k)//确定第k个以及k后面的数字 
{
	for(ll i=1;i<=n;i++)
	{
		if(f[i]==0&&(k==1||isprime(i+a[k-1])))
		{
			a[k]=i;
			f[i]=1;
			if(k==n&&isprime(a[k]+a[1]))
			{
				for(ll j=1;j<=n;j++)
				{
					cout<<a[j];
					if(j==n)
						cout<<endl;
					else
						cout<<" ";
				}
			}
			
			else 
				dfs(k+1);
				
			f[i]=0;//回溯
		}
	}
}

int main()
{
	cin>>n;
	dfs(1);
	
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,a[25];
ll f[25];//判断是否用过

bool isprime(ll n)
{
	if(n==1)
		return false;
	else 
		for(ll i=2;i<=n/i;i++)
			if(n%i==0)
				return false;
	return true;
}

void print(ll x)//输出以1为首的满足条件的排序 
{
	if(a[1]==x)
		for(ll i=1;i<=n;i++)
		{
			cout<<a[i];
			if(i==n)
				cout<<endl;
			else 
				cout<<" ";
		}
}

void dfs(ll k)
{
	for(ll i=1;i<=n;i++)
	{
		if(f[i]==0&&(k==1||isprime(i+a[k-1])))
		{
			a[k]=i;
			f[i]=1;
			if(k==n&&isprime(a[1]+a[k]))
				print(1);
			else 
				dfs(k+1);
				
			f[i]=0;
		}	
	} 
}

int main()
{
	cin>>n;
	dfs(1);
	
	return 0;
}