Prime Ring Problem

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 32872 Accepted Submission(s): 14544

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 Asia 1996, Shanghai (Mainland China)
Recommend JGShining | We have carefully selected several similar problems for you: 1312 1072 1242 1175 1253

题意：要求1-n之间的所有数组成一个圆环，而且要求相邻的两个数相加的和是素数。 思路：因为n的数据范围只是1-20，所以相加的和最大不会超过40，所以把40以内的素数标记出来。然后DFS深搜，符合题意的直接输出就可以了。 、

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         using namespace std; int pv[50]; int n; int p[50]; int v[50]; void getprime() { for(int i=1;i<50;i++) { pv[i] = 1; } for(int i=1;i<=41;i++) { int pi = sqrt(i); for(int j=2;j<=pi;j++) { if(i%j == 0) { pv[i] = 0; break; } } } } void DFS(int cnt,int x) { if(cnt == n && pv[p[n-1]+p[0]] == 1) { for(int i=0;i
        
         ?


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 3307 Smart Sister 打表解因..	下一篇：c++学习 - int 和 string 的相互..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: