Prime Ring Problem

Problem Description

A ring is
compose of n circles as shown in diagram. Put natural number 1, 2,
..., n 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.



Ring Problem" title="Prime Ring Problem">

Input

n (0 < n
< 20).

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. Print solutions in lexicographical order.



You are to write a program that completes above process.



Print a blank line after each case.

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

题意：给你一个n，得到一个数组，1~n；让你写出一个素数环，要求相邻两个数（顺逆时针）和是素数，输出的时候第一个永远是一；

解题思路：按照递归求全排列的思想，从第2个开始递归一直到最后一位，并且首尾也是素数才算是搜索完成；

感悟：一开始我还以为得剪纸，但是只有20个数，一次就过了；

代码：

#include

#include

#include

#include

#define maxn 25

using namespace std;

int ans[maxn],visit[maxn],n;

int Prime(int a)

{

    for(int
i=2;i<=sqrt(a);i++)

       
if(a%i==0)

           
return 0;

    return
1;

}



void dfs(int cur)

{

   
if(cur==n&&Prime(ans[0]+ans[n-1]))//递归到最后一位，并且首尾也能是素数

    {

       
for(int i=0;i

           
printf("%d ",ans[i]);

       
printf("%d\n",ans[n-1]);

    }

    else

    {

       
for(int i=2;i<=n;i++)

       
{

           
if(!visit[i]&&Prime(i+ans[cur-1]))//这个数没用过并且相邻的是素数

           
{

               
ans[cur]=i;

               
visit[i]=1;

               
dfs(cur+1);

               
visit[i]=0;

           
}

       
}

    }

}

int main()

{

   
//freopen("in.txt", "r", stdin);

    int
s=1;

   
memset(visit,0,sizeof(visit));

   
while(~scanf("%d",&n)&&n)

    {

       
for(int i=0;i

           
ans[i]=i+1;

       
printf("Case %d:\n",s++);

       
dfs(1);

       
printf("\n");

    }

}