https://www.luogu.org/problemnew/show/UVA524
1,2,3,4 相邻两个数相加都是素数,符合题意
1,3,2,4 2和4相加不是素数,不符合题意
1,3,4,2 4和2相加不是素数,不符合题意
1,4,2,3 4和2相加不是素数,不符合题意
1,4,3,2 相邻两个数相加都是素数,符合题意。
所以正确的答案为
1,2,3,4
1,4,3,2
1,2,3,4,5 4和5相加不是素数,不符合题意
1,2,3,5,? 3和5相加不是素数,不符合题意
1,2,4,? 2和4相加不是素数,不符合题意
1,2,5,3,? 5和3相加不是素数,不符合题意
1,2,5,4,? 5和4相加不是素数,不符合题意
1,3,? 1和3相加不是素数,不符合题意
1,4,2,? 4和2相加不是素数,不符合题意
1,5,? 1和5相加不是素数,不符合题意
所以n=5时,没有答案。
#include<bits/stdc++.h>
using namespace std;
int n,i,cnt,a[100];
int prime[100];
bool visited[100]; //标记visited[i]是否被用过
void dfs(int pos)
{
for(int i=2; i<=n; i++)
{
if(!visited[i] && prime[a[pos-1] + i]) //i没有用过,且与上一个数的和为素数
{
visited[i] = true; // 标记
a[pos]=i; // 存储
if(pos == n) // 放完了n个数
{
if(prime[a[pos] + 1]) //这是一个环,所以最后一个数和第一个数1相邻
{
for(int j=1;j<n;j++)
{
printf("%d ",a[j]);
}
printf("%d",a[n]); //这里很恶心,行末不能有空格
printf("\n");
}
}
else
{
dfs(pos+1);
}
visited[i] = false; //回溯
}
}
}
int main()
{
// 素数打表
prime[2]=prime[3]=prime[5]=prime[7]=prime[11]=prime[13]=prime[17]=prime[19]=prime[23]=prime[29]=prime[31]=1; //先处理一下素数
while(scanf("%d",&n) == 1)
{
cnt++;
printf("Case %d:\n",cnt);
a[1]=1; //第一个数是1
dfs(2); //从第二个数开始搜
cout << endl;
}
return 0;
}