| Prime Ring Problem |
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers into each circle separately, and the sum of numbers in two adjacent circles should be a prime.
Note: the number of first circle should always be 1.
Input
n (0 < n <= 16)
Output
The output format is shown as sample below. Each row represents a series
of circle numbers in the
ring beginning from 1 clockwisely and anticlockwisely. The order of numbers
must satisfy the above requirements.
You are to write a program that completes above process.
#include<cstdio>
#include<cstring>
bool prm[],vis[];
int a[],n;
bool ck(int x)
{
int i;
for (i=;i*i<=x;i++)
if (x%i==) return ;
return ;
}
void dfs(int p)
{
int i,j,k,x,y,z;
if (p==n+)
{
if (prm[a[n]+a[]])
{
printf("%d",a[]);
for (i=;i<=n;i++)
printf(" %d",a[i]);
printf("\n");
}
return;
}
for (i=;i<=n;i++)
if (vis[i]==&&prm[i+a[p-]])
{
a[p]=i;
vis[i]=;
dfs(p+);
vis[i]=;
}
}
int main()
{
int i,j,k,p,q,x,y,z,t;
bool bbb=;
for (i=;i<=;i++)
prm[i]=ck(i);
a[]=;
t=;
while (scanf("%d",&n)==)
{
if (bbb) printf("\n");
bbb=;
memset(vis,,sizeof(vis));
vis[]=;
printf("Case %d:\n",++t);
dfs();
}
}
素数环。注意边界。注意每组数据间的回车（虽然题上没说）。