Happy Birthday！LevOJ P1305 素数环

思路：

DFS法

AC代码：

#include<bits/stdc++.h>

using namespace std;

int n;
int order=1;
int v[20],a[20];

bool prime(int p){
    bool flag=true;
    if(p==2){
        return true;
    }else{
        for(int i=2;i<p;i++){
            if(p%i==0){
                flag=false;
                break;
            }
        }
    }
    return flag;
}

void dfs(int s){
    if(s==n&&prime(a[1]+a[n])){
        for(int i=1;i<n;i++){
            cout<<a[i]<<" ";
        }
        cout<<a[n]<<endl;
    }else{
        for(int i=2;i<=n;i++){
            if(!v[i]&&prime(a[s]+i)){
                a[s+1]=i;
                v[i]=1;
                dfs(s+1);
                v[i]=0;
            }
        }
    }
}

int main(){
    while(cin>>n){
        cout<<"Case "<<order<<":"<<endl;
        order++;
        memset(v,0,sizeof(v));
        a[1]=1;
        dfs(1);
        cout<<endl;
    }
}

原题链接：https://vjudge.net/problem/UVA-524

注意：UVa的题目格式不能有任何多余空格和换行