Prime Ring Problem HDU - 1016

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 <algorithm> #include <cstdio> #include <cstring> #include <cmath> #define inf 0x3f3f3f3f using namespace std; int book[22]; int a[22]; int is_prime(int x) { for(int i=2;i<=sqrt(x);i++) { if(x%i==0) return 0; } return 1; } void dfs(int n,int k) { if(k>n) { if(is_prime(a[k-1]+a[1])==0) return ; } int i; if(k>n) { printf("%d",a[1]); for(i=2;i<=n;i++) { printf(" %d",a[i]); } printf("\n"); return ; } for(i=2;i<=n;i++) { if(book[i]==0&&is_prime(i+a[k-1])==1) { a[k]=i; book[i]=1; dfs(n,k+1); book[i]=0; } } } int main() { int n,num=0; while(~scanf("%d",&n)) { memset(book,0,sizeof(book)); num++; a[1]=1;book[1]=1; printf("Case %d:\n",num); dfs(n,2); printf("\n"); } return 0; }