昆明旅游网站建设佛山百度seo代理

有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环

有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束

输入

有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。

输出

每组第一行输出对应的Case序号，从1开始。
如果存在满足题意叙述的素数环，从小到大输出。
否则输出No Answer

素数环首先想到如何在一组数据中快速的判断两两之和为素数，则可在开始遍历各种组合之前建立一个素数表，之后有数据和看是否出现在该表中。

素数表的两种保存方式：1：由题n小于20所以两两数之和小于38，所以只需要保存40以内的素数，第一种将所有素数按顺序保存在数组中，对比的时候从头一一对比。2.建立一个数组数组下标作为数字，当它是素数是令其为1否则为0，这时判断时只需将要判断的数作为下标访问数组即可，这里使用第二种更快；

	memset(sa,0,sizeof(sa));for(int ok=1,k=2,j=2;j<40;j++,ok=1)                     /*生成素数表*/ {for(int i=2;i<=j/2;i++){if(j%i==0)	ok=0;}if(ok) sa[j]=1;}

数列的生成：使用递归调用深度优先遍历解答树，此处与全排列的生成方式相同，但在向目标数组一一填入数字时便进行判断，对树进行剪枝。（注：为加快判断将要在目前位置填入的数字是否已经使用，首先建立一个标志数组，以数组下标表示该数当这个数字已被使用让其值为1，没被使用则为0。在递归调用时注意在递归调用之后让该数的值重新为0，即回溯！）

#include <stdio.h>
#include<string.h>
void found(int n,int cur,int a[],int flag[]);
int count,sa[40];
int main(void)
{int i=0,a[20],in[100],flag[20];memset(flag,0,sizeof(flag));memset(sa,0,sizeof(sa));for(int ok=1,k=2,j=2;j<40;j++,ok=1)                     /*生成素数表*/ {for(int i=2;i<=j/2;i++){if(j%i==0)	ok=0;}if(ok) sa[j]=1;}do{scanf("%d",&in[i++]);}while(in[i-1]);a[0]=1;	for(int j=1;j<i;j++){count=1;printf("Case %d:\n",j);if(!(in[j-1]%2)||in[j-1]==1) found(in[j-1],1,a,flag);   /*跳过3以上的奇数加快速度*/ if(count)	printf("No Answer\n");} return 0;
}
void found(int n,int cur,int a[],int flag[])
{if(cur==n&&sa[a[0]+a[cur-1]])    /*不要忘了判断首尾相加是否为素数*/{for(int i=0;i<n;i++)printf("%d ",a[i]);putchar('\n');count=0;}elsefor(int i=2;i<=n;i++)						if(!flag[i]&&sa[i+a[cur-1]])			/*在数组中依次填入满足要求的数*/ {a[cur]=i;flag[i]=1;found(n,cur+1,a,flag);flag[i]=0;                    /*回溯*/}
}

素数表生成（ Eratosthenes筛法）

	for(i=2;i<=sqrt(n);i++)//生成1~n以内素数表if(!number[i])for(j=i*i;j<n;j+=i)number[j]=1;