素数环

时间限制：

1000 ms  |  内存限制：65535 KB

难度：

2

 

描述

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。

为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。

 

输入

有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。

输出

每组第一行输出对应的Case序号，从1开始。 如果存在满足题意叙述的素数环，从小到大输出。 否则输出No Answer。

样例输入

6830

样例输出

Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2Case 3:No Answer ***************************************************************************************************************************************** TimeLimitExceeded

#include 
        
         #include
         
          int a[30],n,used[40];int is_prime(int x){   for(int i=2;i
          
           #include
           
            using namespace std;int a[30],n,used[40];int is_prime(int x){   for(int i=2;i
            
             >n)  {      memset(used,0,sizeof(used)) ;      a[1]=1;   used[1]=1;      cout<<"Case "<
             
              <<":"<
             
            
           
          
         
        

 

******************************************************************************************************************************************

#include 
        
         #include 
         
          using namespace std;int a[30],used[30];int n;int is_prime( int x){for (int i=2; i
          
           >n,n){    memset(used,0,sizeof(used));a[1]=1;     used[1]=1;cout<<"Case "<
           
            <<":\n";if (n%2==0) dfs(1);else if (n==1) cout<<"1\n";else cout<<"No Answer\n";    cout<
           
          
         
        

 

#include <iostream>

#include <string.h>

using namespace std;

int a[30],used[30];

int n;

int is_prime( int x)

{     for (int i=2; i<x; i++) 

                      if (x%i==0)  return 0;

                                        return 1;            }

 

void dfs(int cur)

{         int i;

            if (cur==n && is_prime ( a[1]+a[n] ))

                     {          for (i=1; i<n; i++ )         

                                       cout<<a[i]<<" ";                cout<<a[n]<<"\n";                return ; 

                            }

 

              for (i=2; i<=n;i++)

         { 

               if (  used[i]==0 &&  is_prime ( a[cur]+i ) )  

 

                                    { a[cur+1]=i ; used[i]=1;  dfs(cur+1);  used[i]=0; }

 

         }

}

int main( )

{       

       int c=1;

             while (cin>>n,n)

       { 

                memset(used,0,sizeof(used));

                     a[1]=1;  used[1]=1;

                        cout<<"Case "<<c++<<":\n";

               if (n%2==0)                    dfs(1);

                   else            if (n==1)                cout<<"1\n";

                                          else                          cout<<"No Answer\n"; 

                                                                    cout<<endl;

                }

              return 0;

}       

 

 

 

 

 

#include
        
         #include
         
          int prime[12]={
      2,3,5,7,11,13,17,19,23,29,31,37};int p[30],used[30],n;int IsPrime(int num){    int j;    for (j=0;j<12;j++) if (num==prime[j]) return 1;    return 0;}void DFS(int i){    int j;    if (i==n&&IsPrime(p[n]+p[1]))    {        for (j=1;j
         
        

 

 

#include<stdio.h>

#include<stdlib.h>

 

int prime[12]={2,3,5,7,11,13,17,19,23,29,31,37};

int p[30],used[30],n;

 

int IsPrime(int num)

           {    

                             int j;   

           for (j=0;j<12;j++)

                    if (num==prime[j])              return 1;   

                                    return 0;              

               }

 

void DFS(int i)

{   

  int j;

    if (i==n&&IsPrime(p[n]+p[1]))

    {  

       for (j=1;j<n;j++) printf("%d ",p[j]);

        printf("%d\n",p[j]);

        return;  

                       }

            for (j=2;j<=n;j++)

   

              {         if ( used[j]==0 && IsPrime(p[i]+j) )

                                               {             p[i+1]=j;             used[j]=1;             DFS(i+1);             used[j]=0;         }

                }

  }

 

int main()

{   

  int i=1,j;

    while (scanf("%d",&n) && n )

    {

        for (j=0;j<30;j++)         used[j]=0;

        printf("Case %d:\n",i++);         p[1]=1;

                     if (n%2==0 || n==1)            DFS(1);

                                else                       printf("No Answer\n");

    }

    return 0;

}