Prime Ring Problem

** Title Description **:
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

** Explanation of the title **:

Enter an integer , Form these numbers into a closed loop , It is the sum of two adjacent numbers that makes them a prime number . Output from 1 At the beginning , Each number takes once .

** Topic ideas **:

1： In the simplest and original way , Sort numbers , Then judge whether it is right or wrong .（ Because the number is too large , stay 12 when , The code is already running very slowly , To 16 Cannot run while . Students who don't believe can try ！）

2： Use backtracking , from 1 Start experimenting one by one , Go down if you can , Experiment with unused numbers , If it doesn't work , Then go back . It's a recursive process . It will run much faster .

**AC Code :**

#include<cstdio>
int prime[]={2,3,5,7,11,13,17,19,23,29,31,37};// Put possible primes in it 
int arr[20],vis[20];
int n;

bool is_prime(int num)// Judge whether sum is prime 
{
    for(int i=0;i<12;i++)
        if(prime[i]==num)return true;
    return false;
}
void dfs(int cur)// Backtracking method to find the realizable ring .
{
    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':' ');// Printing requirements 
    }
    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)// Input requirements 
    {
        if(cnt)printf("\n");// Judge case Output 
        printf("Case %d:\n",++cnt);
        arr[0]=1;
        dfs(1);
    }
    return 0;
}