首页 > 代码库 > nyoj 488素数环
nyoj 488素数环
素数环
时间限制:1000 ms | 内存限制:65535 KB
难度:2
描述
有一个整数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
/* 素数环:给定n,1~n组成一个素数环,相邻两个数的和为素数。 首先偶数(2例外,但是本题不会出现两个数的和为2)不是素数, 所以素数环里奇偶间隔。如果n是奇数,必定有两个奇数相邻的情况。 所以当n为奇数时,输出“No Answer”。 当n == 1时只1个数,算作自环,输出1 所有n为偶数的情况都能变成奇偶间隔的环-----所以都有结果。 */ #include<stdio.h> #include<string.h> int prime[40]; int visit[21]; int a[21]; void Is_prime() { int i,j; prime[0]=prime[1]=1; for(i=2;i<=6;++i) for(j=i*i;j<40;j+=i) prime[j]=1; } void DFS(int k,int n) { int i; if(k==n+1&&prime[a[n]+a[1]]==0) { printf("1"); for(i=2;i<=n;++i) printf(" %d",a[i]); printf("\n"); return; } for(i=2;i<=n;++i) { if(!visit[i]&&!prime[i+a[k-1]]) { visit[i]=1; a[k]=i; DFS(k+1,n); visit[i]=0; } } } int main() { int T,n; T=1; Is_prime(); while(scanf("%d",&n),n) { printf("Case %d:\n",T++); if(n==1) { printf("1\n"); continue; } if(n&1) { printf("No Answer\n"); continue; } memset(visit,0,sizeof(visit)); visit[1]=a[1]=1; DFS(2,n); } return 0; }
nyoj 488素数环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。