本文共 1452 字，大约阅读时间需要 4 分钟。

#include
   
    #include
    
     #include
     
      int prime (int m) {   	for(int i=2; i<=sqrt(m); i++)		if(m%i==0) return 0;	return 1;}int book[1000],a[1000],n;//a[]存数据void bfs(int x) {   	int i,j,k,l;	if(x==n+1&&prime(1+a[n])==1) {   		printf("1");		for(i=2; i<=n; i++)			printf(" %d",a[i]);	printf("\n");	}	else {   		for(i=2; i<=n; i++) {   			if(book[i]==0&&prime(a[x-1]+i)==1) {   				a[x]=i;				book[i]=1;				bfs(x+1);				book[i]=0;			}		}	}}int main() {   	int c=1;	while(~scanf("%d",&n)) {   		memset(book,0,sizeof(book));		memset(a,'\0',sizeof(a));		printf("Case %d:\n",c++);		book[1]=1;		a[1]=1;		bfs(2);		printf("\n");	}}
     
    
   

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

Sample Output

Case 2:

Source