Prime Ring Problem

**题目描述**:
A ring is composed of n (even number) circles as shown in diagram. Put natural numbers 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.

 
>**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.
 

>**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

**题目解释**:

输入一个整数，将这些数字组成一个闭合环，是他们相邻两数和为一个素数。输出要从1开始的，每个数字取 一次。

**题目思路**:

1：用最简单原始的方法，将数字进行排序，然后进行判断对或者错。（由于数字过于庞大，在12时，代码运行已经很慢了，到16时无法运行。不信的同学可以去试试！）

2：使用回溯法，从1开始一个一个进行试验，如果可以就向下进行，拿没有用过的数字进行试验，如果无法成功，则进行回溯。是一个递归的过程。运行的速度会快很多。

**AC代码:**

#include<cstdio>
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37};//将有可能出现的素数放在里面
int arr[20],vis[20];
int n;

bool is_prime(int num)//判断和是否是素数
{
    for(int i=0;i<12;i++)
        if(prime[i]==num)return true;
    return false;
}
void dfs(int cur)//回溯法寻找可以实现的环。
{
    if(cur==n && is_prime(arr[0]+arr[n-1]))
    {
        for(int i=0;i<n;i++)
            printf("%d%c",arr[i],i==n-1?'\n':' ');//打印需求
    }
    else for(int i=2;i<=n;i++)
        {
            if(!vis[i] && is_prime(i+arr[cur-1]))
            {
                arr[cur]=i;
                vis[i]=1;
                dfs(cur+1);
                vis[i]=0;
            }
        }
}
int main()
{
    int cnt=0;
    while(scanf("%d",&n)!=EOF)//输入需求
    {
        if(cnt)printf("\n");//判断case的输出
        printf("Case %d:\n",++cnt);
        arr[0]=1;
        dfs(1);
    }
    return 0;
}