HDU 1016 Prime Ring Problem

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input

n (0 < n < 20).

Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input

6
8

Sample Output

Case 1:
1 4 3 2 5 6
1 6 5 2 3 4

Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

题目大意：

这是一个求素数环的问题。输入为多组实例测试，输入n，从1到n组成一个环，要求环上相邻两个数相加为素数。

c++

#include<iostream>
#include<stack>
#include<cstring>
#include<cmath>
using namespace std;
int m,n,q;         //m表示环是从1到m,n用来统计合适的个数
int f[30],s[30];   //f用来存放环上元素,s用来标记是否已在环上
int zs(int a)      //素数判断
{
    int c,d,e,f;
    c=sqrt(a);
    for(d=2;d<=c;d++)
    {
        if(a%d==0)
            return 1;
    }
    return 0;
}
void dfs()        //递归
{
    int a,b,c,d,e;
    if(n==m&&zs(f[1]+f[m])==0)  //当环上个数与输入m相等并且满足第一个加最后一个仍是素数时输出
    {
        for(a=1;a<m;a++)
        {
            cout<<f[a]<<" ";
        }
        cout<<f[n]<<endl;
        return ;
    }
    for(b=1;b<=m;b++)
    {
        if(zs(b+f[n])==0&&s[b]!=1)  //判断b加环上的上一个元素是素数并且b不在环上进行递归
        {
            s[b]=1;
            n++;
            f[n]=b;
            dfs();
            n--;
            s[b]=0;
        }
    }
    return ;
}
int main()
{
    int a,b,c,d;
    q=1;
    while(cin>>m)
    {
        n=1;
        memset(f,0,sizeof(f));
        memset(s,0,sizeof(s));
        f[1]=1;s[1]=1;
        cout<<"Case "<<q<<":"<<endl;
        q++;
        dfs();
        cout<<endl;
    }
    return 0;
}