......................
1 #include <iostream> 2 #include <string.h> 3 #include <string> 4 #include <queue> 5 #include <algorithm> 6 #include <cstdio> 7 #include <cmath> 8 using namespace std; 9 bool vit[21]; 10 bool prim[10000]; 11 int n; 12 bool isprim(int n){ 13 int i; 14 for(i=2;i<=sqrt(n);++i){ 15 if(n%i==0) return false; 16 } 17 return true; 18 } 19 void init(){ 20 int i; 21 for(i=2;i<10000;++i){ 22 if(isprim(i)==1) prim[i]=1; 23 else prim[i]=0; 24 } 25 return ; 26 } 27 28 void dfs(int step,string str){ 29 // cout<<str<<endl; 30 int i,j; 31 int temp,begin; 32 string t; 33 if(step==n+1){ 34 printf("%d",str[0]-'a'+1); 35 //cout<<str[0]; 36 for(i=1;i<str.length();++i){ 37 // cout<<" "<<str[i]; 38 printf(" %d",str[i]-'a'+1); 39 } 40 printf(" "); 41 //cout<<endl; 42 return ; 43 } 44 for(i=1;i<=n;++i){ 45 if(vit[i]==1) continue; 46 t="0"; 47 t[0]=i+'a'-1; 48 t=str+t; 49 temp=t[step-2]-'a'+1; 50 if(step==n&&prim[temp+i]==1&&prim[1+i]==1){ 51 // cout<<"yeah! "; 52 vit[i]=1; 53 dfs(step+1,t); 54 vit[i]=0; 55 }else if(step!=n&&prim[temp+i]==1){ 56 // cout<<"???"<<endl; 57 vit[i]=1; 58 dfs(step+1,t); 59 vit[i]=0; 60 } 61 } 62 return ; 63 } 64 int main(){ 65 int cnt=1; 66 init(); 67 // while(cin>>n) 68 // if(prim[n]==1) cout<<"yes"<<endl; 69 // else cout<<"no"<<endl; 70 // while(cin>>n){ 71 while(~scanf("%d",&n)){ 72 // cout<<"Case "<<cnt++<<":"<<endl; 73 printf("Case %d: ",cnt++); 74 vit[1]=1; 75 dfs(2,"a"); 76 // cout<<endl; 77 printf(" "); 78 } 79 return 0; 80 } 81 82 83 84 85 86