Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 34108    Accepted Submission(s): 15098

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

 

 

Source

 

 

Recommend

JGShining   |   We have carefully selected several similar problems for you:            

RE:素数环， 字典序输出；

1 #include 
      
         2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 int dis[30], vis[30], my[30]; 7 int n; 8 int is_prime(int a)     //判断素数；  9 {10 11     if(a == 1 || a == 0)12         return 0;13     if(a == 2)14         return 1;15     else16     {17         for(int i=2; i <= sqrt(a); i++)         //不要忘记等号；18         {19             if(a % i == 0)20                 return 0; 21         }22         return 1;23     }24 } 25 void Dfs(int a)26 {27     int i;28     if(a == n && is_prime(dis[n-1] + dis[0]))29     {30         for(i = 0; i < n; i++)31         {32             if(i > 0)33                 printf(" ");34             printf("%d", dis[i]);35         }36         printf("\n");37         return;               //子循环结束； 38     }39     for(i=2; i<=n; i++)40     {41         if(!vis[i] && is_prime(dis[a - 1] + i))42         {43             vis[i] = 1;44             dis[a] = i;45             Dfs(a  + 1);46             vis[i] = 0;47         }48     }49 }50 int main()51 {52     int i, j = 1;53     while(~scanf("%d", &n))54     {55         memset(vis, 0 , sizeof(vis));56         printf("Case %d:\n", j++);57         vis[0] = 1;58         dis[0] = 1;59         Dfs(1);60         printf("\n");61     }62     return 0; 63 }