hdu 1016 （DFS）

注意最後一個要與1的和為素！！

[cpp]
#include"stdio.h"  
#include"string.h"  
int prime[44]; 
int mark[22]; 
int a[22],n; 
 
void dfs(int k,int m) 
{ 
    a[k]=m; 
    int i; 
    if(k==n) 
    { 
        //注意最後一個要與1的和為素！！  
        if(!prime[m+1])return ; 
        for(i=1;i<n;i++) 
            printf("%d ",a[i]); 
        printf("%d\n",a[i]); 
        return ; 
    } 
    for(i=2;i<=n;i++) 
    { 
        if(prime[i+m]&&!mark[i]) 
        { 
            mark[i]=1; 
            dfs(k+1,i); 
            mark[i]=0; 
        } 
    } 
} 
 
int main() 
{ 
    int i,k; 
    memset(prime,0,sizeof(prime)); 
    prime[2]=prime[3]=prime[5]=prime[7]=1; 
    prime[11]=prime[13]=prime[17]=prime[19]=prime[23]=1; 
    prime[29]=prime[31]=prime[37]=prime[41]=1; 
    k=1; 
    while(scanf("%d",&n)!=-1) 
    { 
        memset(mark,0,sizeof(mark)); 
        printf("Case %d:\n",k++); 
        dfs(1,1); 
        printf("\n"); 
    } 
    return 0; 
} 
         

#include"stdio.h"
#include"string.h"
int prime[44];
int mark[22];
int a[22],n;

void dfs(int k,int m)
{
 a[k]=m;
 int i;
 if(k==n)
 {
  //注意最後一個要與1的和為素！！
  if(!prime[m+1])return ;
  for(i=1;i<n;i++)
   printf("%d ",a[i]);
  printf("%d\n",a[i]);
  return ;
 }
 for(i=2;i<=n;i++)
 {
  if(prime[i+m]&&!mark[i])
  {
   mark[i]=1;
   dfs(k+1,i);
   mark[i]=0;
  }
 }
}

int main()
{
 int i,k;
 memset(prime,0,sizeof(prime));
 prime[2]=prime[3]=prime[5]=prime[7]=1;
 prime[11]=prime[13]=prime[17]=prime[19]=prime[23]=1;
 prime[29]=prime[31]=prime[37]=prime[41]=1;
 k=1;
 while(scanf("%d",&n)!=-1)
 {
  memset(mark,0,sizeof(mark));
  printf("Case %d:\n",k++);
  dfs(1,1);
  printf("\n");
 }
 return 0;
}