HDOJ 1016 Prime Ring Problem素数环【深搜2】

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int n;
int df[21];
int t=1;
int m[21];
int mi;
bool pn(int x,int y){//判断素数
    for(int i=2;i*i<=x+y;i++){
        if((x+y)%i==0){
            return false;
        }
    }
    return true;
}
void dfs(int x){
    if(mi==n&&pn(m[1],m[n])){
        for(int i=1;i<n;i++){
            printf("%d ",m[i]);
        }
        printf("%d\n",m[n]);
        return;
    }
    for(int i=2;i<=n;i++){
        if(df[i]==0&&pn(x,i)){
            df[x]=1;
            mi++;//当前小球数
            m[mi]=i;
            dfs(i);
            df[x]=0;
            mi--;//必须减一
        }
    }
}
int main()
{
    while(~scanf("%d",&n)){
        printf("Case %d:\n",t);
        t++;
        memset(df,0,sizeof(df));
        mi=1;
        m[mi]=1;
        dfs(1);
        printf("\n");
    }
    return 0;
}