Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 48754    Accepted Submission(s): 21488 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.   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

#include <iostream> #include <stdio.h> #include <algorithm> #include <string.h> using namespace std; int l=0; int n; int p[14]={2,3,5,7,11,13,17,19,23,29,31,37,41}; int vis[21],d[21]; bool isprime(int k) { for(int i=0; i<14; i++) { if(p[i] == k) return true; } return false; } void dfs(int pos) { if(pos == n&&isprime(d[0]+d[n-1])) { for(int i=0; i<n; i++) printf(i == n-1?"%d\n":"%d ",d[i]); } else for(int i=2; i<=n; i++) { if(!vis[i]&&isprime(i+d[pos-1])) { d[pos] = i; vis[i] = 1; dfs(pos+1); vis[i] = 0; } } } int main() { int t=0; while(~scanf("%d",&n)) { t++; memset(vis,0,sizeof vis); printf("Case %d:\n",t); d[0]=1; dfs(1); printf("\n"); } return 0; }