hdu 1016 Prime Ring Problem

题目大体意思：就是给定一个n，有1。。n这n个数，组成一个环，保证相邻两个数的和是素数

求所有满足条件的序列

 

解题思路：序列从小到大，可以让x[1]=1 然后其他的各位采用搜索方法就可以了

 

其中有个地方可以优化一下，就是求素数可以先把40以内的素数求出来，通过数组标记一下就可以，不必要每次都调用判断素数的函数

/////hdu 500多ms过的//////

#include
const int size=25;
int n;
int x[size],use[size];

int prime(int x)
{
    int i;
    for(i=2;i*i<=x;i++)
        if(x%i==0) return 0;
    return 1;
}

void recur(int p)
{
    int i;
   for(x[p]=2;x[p]<=n;x[p]++)
   {
       if(use[x[p]]==1) continue;
      
       if(prime(x[p-1]+x[p])==0) continue;

       use[x[p]]=1;
       if(p       else
       {
           //还必须判断下x[n]和x[1]的和是否是素数
           if(prime(x[n]+x[1]))
           {
           //从小到大打印
           for(i=1;i           printf("%d\n",x[n]);
           }
       }
       ////
       use[x[p]]=0;
   }
}

int main()
{
    int cas=1;
    while(scanf("%d",&n)!=EOF)
    {
     //if(cas!=1) printf("\n");
     printf("Case %d:\n",cas++);
     x[1]=1;
     recur(2);
     printf("\n");
    }
}

////////////////////

//修改后的时间减少了不少 hdu 100多ms过的 但zju还是过不了

//后来发现n为奇数的时候没有解，我却搜了，浪费了好多时间

//修改之后再zju马上过了，00.00.41过的

//////////////////////////

#include
#include
const int size=25;
int n;
int x[size],use[size],prime[size*2];

void recur(int p)
{
    int i;
   for(x[p]=2;x[p]<=n;x[p]++)
   {
       if(use[x[p]]==1) continue;
      
       if(prime[x[p-1]+x[p]]==0) continue;

       use[x[p]]=1;
       if(p       else
       {
           //还必须判断下x[n]和x[1]的和是否是素数
           if(prime[x[n]+x[1]])
           {
           //从小到大打印
           for(i=1;i           //{putchar(x[i]+'0');putchar(' ');}
           //putchar(x[n]+'0');
           //putchar('\n');  大于等于10的数就不可以了
          {
          if(x[i]>9) {putchar(x[i]/10+'0');putchar(x[i]%10+'0');}
          else putchar(x[i]+'0');
          putchar(' ');                  
          }
          //printf("%d ",x[i]);
          //printf("%d\n",x[n]);
          if(x[n]>9) {putchar(x[n]/10+'0');putchar(x[n]%10+'0');}
          else putchar(x[n]+'0');
          putchar('\n');
           }
       }
       ////
       use[x[p]]=0;
   }
}

int main()
{
    int i,cas=1;
    memset(prime,0,sizeof(prime));
    prime[2]=1;prime[3]=1;prime[5]=1;prime[7]=1;prime[11]=1;prime[13]=1;
    prime[17]=1;prime[19]=1;prime[23]=1;prime[29]=1;prime[31]=1;prime[37]=1;

    while(scanf("%d",&n)!=EOF)
    {
     //if(cas!=1) printf("\n");
     printf("Case %d:\n",cas++);
     x[1]=1;
     recur(2);   //只要这里改下 if(n%2==0) recur(2);
     //printf("\n");
     putchar('\n');
    }
}