Prime Ring 补充素数筛选表

素数环问题经单的深搜题目；

题意是这样的：

给你n个数（n<=20）：1，2，3，4，5....n；把这n个数围成一个圈，每相邻的两个数之和为素数，而且，第一个数必须是1，以避免不必要的重复；

题意很简单，关键是程序的实现，这就用到了深搜；

先说什么是深搜，就是不撞南墙不回头，找准一个方向不达目的誓不罢休，也就是暴力枚举加上限制条件，再通过递归实现；

那么，说说这个题的思路：

假设n是6；

因为第一个必须是1，所以直接从第二个数找；把2放在第二个数的位置，判断1+2=3是素数，在找第三个，把3放在这里，判断2+3=5是素数；第四个放4，3+4=7是素数；第五个放5，4+5=9不是素数，第五个放6，4+6=10不是素数； 6后边没有数可用，再返回第四个，5放在第四个格子，3+=8不行；放6，3+6=9，不行，返回第三个格子，放4，2+4=6，不行；放5，2+5=7可以，再到第四个格子，注意前边已经放了1，2，5，所以这三个数不能用，放3，5+3=不行；放4，5+4=9不行，放6，5+6=11可以，第五个格子，放3，6+3=9不行，放4，6+4=10，不行，返回第五个格子，返回第四个格子，第四个格子已经试到6，返回第三个格子，放6，2+6=8不行，返回第二个格子，放3，1+3=4不行；放4，1+4=5可以，第三个格子，放2不行，放3可以；第四个格子放2可以，第五个放5可以，第六个放6可以，注意六个数虽然已经找完，但他是个环，所以还要判断最后一个和第一个的和：6+1=7可以，所以1，4，3，2，5，6是一种答案；

是不是已经看晕了呢？下面再看看这部分的实现代码：

void dsf(int step){  //step表示第几步，放第几个数；
    if(step==n+1){    //n个数放完，判断第一个和最后一个和是否为素数；
        if(prime[1+a[step-1]])
            print();
        return;
    }
    int i;

    for(i=2; i<=n; i++){

        if(prime[i+a[step-1]] && !book[i]){
            a[step]=i;
            book[i]=1;   //标记该数已使用；
            dsf(step+1);
            book[i]=0;//标记清除，一定不要忘记这一步；
        }
    }
    return;
}

其中有个素数的判断，因为范围不大，直接建个表，prime[40],是素数标记为1，反之标记为0；

void IsPrime(){//初始化prime数组全为1；
    int i, j;
    for(i=2; i<=40; i++)
        if(prime[i])//prime[i]==1，i是素数，则i的倍数不是素数，标记为0；
        for(j=i+i; j<=40; j+=i)
        prime[j]=0;
    return;
}

下面奉上全部代码：

#include 
#include 
int prime[45];
int book[45];
int a[25];
int n;
void IsPrime(){
    int i, j;
    for(i=2; i<=40; i++)
        if(prime[i])
        for(j=i+i; j<=40; j+=i)
        prime[j]=0;
    return;
}
void print(){
    int i;
    for(i=1; i<=n; i++){
        if(i==n)
            printf("%d\n",a[i]);
        else
            printf("%d ",a[i]);
    }
    return;
}
void dsf(int step){
    if(step==n+1){
        if(prime[1+a[step-1]])
            print();
        return;
    }
    int i;

    for(i=2; i<=n; i++){

        if(prime[i+a[step-1]] && !book[i]){
            a[step]=i;
            book[i]=1;
            dsf(step+1);
            book[i]=0;
        }
    }
    return;
}
int main(){
    int cnt=0;
    while((scanf("%d",&n))!=EOF){
        cnt++;
        int i;
        printf("Case %d:\n",cnt);
        for(i=2; i<=40; i++){
            prime[i]=1;
            book[i]=0;
        }
        IsPrime();
        a[1]=1;
        book[1]=1;
        dsf(2);
        printf("\n");
    }
    return 0;
}