Prime Ring Problem问题

题目链接

题目概述

给定一个n，要求将从1…n这些数字按一定顺序围成圆圈，使得相邻两个数字之和为素数，且第一个数字一定为1，要求输出可能的序列。

解题思路

首先，放置数字的问题，类似于n个数字的全排列，这里的要求是相邻数字和为素数，那么要注意，到了放置第n个数字时，需要考察它与1的和是否也为素数。 那么这里首先涉及了一个问题—判断一个数是否为素数(方法见下方)。我们从第1个位置到第n个位置，依次放置数字，循环遍历1到n的数字，判断每个数是否已经放置过，若没有放置过，则看它与前一个数字的和是否为素数。直到放置第n个数字时，判断与1的和是否为素数。

判断素数
因为这里题目给的n比较小，范围在0和20之间。
第一种方法：首先1到20的数字，两个数和为质数，那么这个质数最大为39，即19+20；那么可以用map来标记1—39内的质数。若k为质数，则map[k] = 1；
代码如下：

map<int,int>mp; mp[2]=mp[3]=mp[5]=mp[7]=mp[11]=mp[13]=mp[17]=mp[19]=1; mp[23]=mp[29]=mp[31]=mp[37]=mp[39]=1; 

第二种方法：用一个数组来标记1到40内的数字，若下标 i 对应的值为1，则 i 为非素数；若下标 i 对应的值为0，则表示该数为素数。
代码如下：

int noprime[40]; noprime[1]=1;  for(int i=2;i<=40;i++)  if(!noprime[i])   for(int j=2*i;j<=40;j=j+i)    noprime[j]=1; 

具体代码如下

#include<cstdio> #include<map> #include<cstring> #include<algorithm> using namespace std;  map<int,int>mp; int n; int a[22]; bool vis[22]; int an = 0; void dfs(int x) { if(x == n+1) { //如果此时到了n+1个位置，就需要判断第n个数字和1的和 if(mp[a[n]+1]==1) { for(int i = 1; i<= n; i++) { //直接输出结果 if(i == n) { printf("%dn",a[i]); } else { printf("%d ",a[i]); } } } return; } for(int i = 2; i<= n; i++){ if(!vis[i] && mp[a[x-1]+i]==1) { //如果该数没有放置过，且与前一个数字的和为素数，满足条件    a[x] = i;    vis[i] = true; //标记该数字已经放置过 dfs(x+1);    vis[i] = false; //回溯 } } return; } int main() {  a[1] = 1; //下面为标记素数  mp[2]=mp[3]=mp[5]=mp[7]=mp[11]=mp[13]=mp[17]=mp[19]=1;   mp[23]=mp[29]=mp[31]=mp[37]=mp[39]=1; while(scanf("%d",&n)!=EOF) { memset(vis,false,sizeof(vis));   an++; printf("Case %d:n",an); dfs(2); //第一个数字为1，直接从第二个数字开始放置 printf("n"); } }