南阳市理工-题目488素数环
南阳理工---题目488素数环
- 描述
-
有一个整数n,把从1到n的数字无重复的排列成环,且使每相邻两个数(包括首尾)的和都为素数,称为素数环。
为了简便起见,我们规定每个素数环都从1开始。例如,下图就是6的一个素数环。
- 输入
- 有多组测试数据,每组输入一个n(0<n<20),n=0表示输入结束。
- 输出
- 每组第一行输出对应的Case序号,从1开始。
如果存在满足题意叙述的素数环,从小到大输出。
否则输出No Answer。 - 样例输入
-
6 8 3 0
- 样例输出
-
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 Case 3: No Answer
- 来源
- hdu改编
- 上传者
-
ACM_丁国强
分析:给定一个n,从1—n组成一个素数环,每相邻两个数之和是素数,需要考虑两种情况第一:如果n=1则应该输出1,第二:如果n是奇数那么就不能组成素数环,因为两个奇数的和不是素数,代码如下:
#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> using namespace std; #define N 50 bool a[N]; int vis[N],ring[N]; void dfs(int k,int n) //深搜 { if(k==n+1&&a[ring[1]+ring[n]]) { printf("1"); for(int i=2;i<=n;i++) { printf(" %d",ring[i]); } printf("\n"); } for(int i=2;i<=n;i++) { if(!vis[i]&&a[i+ring[k-1]]) { vis[i]=1; ring[k]=i; dfs(k+1,n); vis[i]=0; } } } int main() { int n; int test=1; while(cin>>n) { if(n==0) break; printf("Case %d:\n",test++); if(n==1) printf("1\n"); else if(n%2) printf("No Answer\n"); else if(n%2==0) { memset(vis,0,sizeof(vis)); //标记数组 memset(a,true,sizeof(a)); for(int i=2;i<sqrt(N);i++) //素数的判断 { if(!a[i]) continue; for(int j=i*i;j<N;j+=i) { a[j]=false; } } ring[1]=vis[1]=1; dfs(2,n); } } return 0; }
-