素数环问题[XDU1010]

时间:2022-02-08 16:34:04
Problem 1010 - 素数环问题
Time Limit: 1000MS   Memory Limit: 65536KB   Difficulty:
Total Submit: 972  Accepted: 223  Special Judge: No
Description

  有一个由n个数字相连组成的圆环(n<20),组成圆环的数字分别为1,2,3...n-1,n.要求每两个相邻元素的和为素数。(注意:第一个元素始终为1)。

Input
n (0<n<20)
Output
要求输出所有符合条件的组成圆环的元素,每个符合条件的圆环按顺时针或者逆时针将元素依次输出,输出格式见样例。要求按字典序输出。
每例以空行分开。
Sample Input
6
8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

Hint
 
Source
Wang Miao
好像很眼熟,似乎在HDU上见过.
#include<stdio.h>
#include<string.h>
int p[];
bool f[],s[];
int n;
void getprime()
{
int i,j;
memset(f,true,sizeof(f));
f[]=f[]=false;
for (i=;i<;i++)
if (f[i])
for (j=i+i;j<;j+=i) f[j]=false;
}
void print()
{
int i;
for (i=;i<n;i++) printf("%d ",p[i]);
printf("%d\n",p[n]);
}
void dfs(int x)
{
if (x==n)
{
if (f[p[x]+]) print();
return;
}
int i;
for (i=;i<=n;i++)
if (!s[i])
{
if (f[p[x]+i])
{
p[x+]=i;
s[i]=true;
dfs(x+);
s[i]=false;
}
}
}
int main()
{
int cas;
getprime();
for (cas=;scanf("%d",&n)!=EOF;cas++)
{
printf("Case %d:\n",cas);
p[]=;
memset(s,false,sizeof(s));
s[]=true;
dfs();
printf("\n");
}
return ;
}