Prime Ring Problem

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. 

 

Inputn (0 < n < 20). 
OutputThe 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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<sstream>
using namespace std;
int n,A[30];
int vis[30];
int isp[50];
bool is_prime(int i)
{
    int t=0;
    if (i == 2 || i == 1)
        return 1;
    for (int j = 2; j < i; j++)
    {
        if (i % j == 0)
            t++;
    }
    if (t != 0)
        return 0;
    else
        return 1;
}
void dfs(int cur)
{
    if (cur == n && isp[A[0] + A[n - 1]])
    {
        for (int i = 0; i < n; i++)
        {
            if (i != n - 1)
                printf("%d ", A[i]);
            else
                printf("%d", A[i]);
        }
        printf("
");
    }
    else for(int i=2;i<=n;i++)
        if (!vis[i] && isp[i + A[cur - 1]])
        {
            A[cur] = i;
            vis[i] = 1;
            dfs(cur + 1);
            vis[i] = 0;
        }
}
int main()
{
    int t=1;
    for (int i = 1; i <= 50; i++)
        isp[i] = is_prime(i);
    while (cin >> n)
    {
        printf("Case %d:
", t);
        memset(A, 0, sizeof(A));
        for (int i = 0; i <= n; i++)
            A[i] = i+1;
        memset(vis, 0, sizeof(vis));
        dfs(1);
        t++;
        printf("
");
    }
}