素数环

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 using namespace std;
 7 
 8 int prime[13]={2,3 ,5,7,11,13,17,19,23,29,31,37,41};   //素数表 
 9 int s[21] ,vis[21];  //存放当前数s，vis 标记
10 int n,case1=1;
11 
12 bool ans(int cu,int i)  //判断相邻的数的和想加是否为素数
13 {
14     int x=s[cu-1]+i;  
15     for(int j=0;j<13;j++)
16     {
17         if(prime[j]==x)
18             return true;
19     }
20     return false;
21 }
22 void dfs(int cur)  //搜索
23 {
24     
25     if(cur==n+1)
26     {
27         if(ans(n+1,s[1]))
28         {
29             for(int i=1;i<=n;i++)
30                 printf("%d ",s[i]);
31             printf("
");
32             return ;
33         }
34     }
35     for(int i=2;i<=n;i++)
36     {
37         if(!vis[i]&&ans(cur,i))
38         {
39             vis[i]=1;
40             s[cur]=i;   dfs(cur+1);
41             vis[i]=0;
42         }
43     }
44 }
45 
46 int main()
47 {
48    while(scanf("%d",&n)&&n!=0)
49    {
50        printf("Case %d:
",case1++);
51        memset(vis,0,sizeof(vis));
52        s[1]=1;
53        vis[1]=1;
54        if(n==1)
55        {
56            printf("1
");
57            continue;
58        }
59        if(n&1)
60         {
61             printf("No Answer
");
62             continue;
63         }
64         dfs(2);
65    }
66    return 0;
67 }
68         
69

View Code

素数环:给定n，1~n组成一个素数环，相邻两个数的和为素数。
首先偶数(2例外，但是本题不会出现两个数的和为2)不是素数，
所以素数环里奇偶间隔。如果n是奇数，必定有两个奇数相邻的情况。
所以当n为奇数时，输出“No Answer”。
当n == 1时只1个数，算作自环，输出1
所有n为偶数的情况都能变成奇偶间隔的环-----所以都有结果。