摘要：
素数环题目：输入正整数n，把整数1。使得相邻两个整数之和均为素数。输出时从整数1開始逆时针排列。同一个环应该恰好输出一次。n2#include3#include4#include5usingnamespacestd;67constintmaxn=1e3;8intisp[maxn];9intA[maxn];10intn;11intans=0;1213intis_prime{14for{15ifreturn0;16}17return1;18}1920intmain(){21cin>>n;22forisp[i]=is_prime;/*生成素数表，加快后续判断*/23forA[i]=i+1;24do{25intflag=1;26for{27if(!isp[A[i]+A[(i+1)%n]]){/*不是素数，这种排列方式行不通*/28flag=0;29break;30}31}32if{33ans++;34forcout>n;40memset;41forisp[i]=is_prime;42A[0]=1;/*题目中规定从1开始*/43dfs;44cout
素数环
题目：输入正整数n，把整数1。2，3，...，n组成一个环。使得相邻两个整数之和均为素数。
输出时从整数1開始逆时针排列。
同一个环应该恰好输出一次。n<=16
分析：首先运用普通方法（生成测试法）
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespacestd; 6 7 const int maxn =1e3; 8 intisp[maxn]; 9 intA[maxn]; 10 intn; 11 int ans=0; 12 13 int is_prime(intx){ 14 for( int i=2; i*i<=x; i++){ 15 if(x%i==0) return 0; 16 } 17 return 1; 18 } 19 20 intmain(){ 21 cin>>n; 22 for( int i=2; i<=n*2; i++ ) isp[i]=is_prime(i);/*生成素数表，加快后续判断*/ 23 for( int i=0; i<n; i++ ) A[i]=i+1; 24 do{ 25 int flag=1; 26 for(int i=0; i<n; i++){ 27 if(!isp[A[i]+A[(i+1)%n]]){/*不是素数，这种排列方式行不通*/ 28 flag=0; 29 break; 30 } 31 } 32 if(flag){ 33 ans++; 34 for( int i=0; i<n; i++ ) cout<<A[i]<<" "; 35 cout<<endl; 36 } 37 }while(next_permutation(A+1,A+n));/*第一个位置是1！*/ 38 cout<<ans<<endl; 39 return 0; 40 }
这种方法当n=12就已经很慢了，n=16无法输出结果。。。
思路二：回溯法。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespacestd; 5 6 const int maxn =1000; 7 intvis[maxn]; 8 intA[maxn]; 9 intisp[maxn]; 10 intn; 11 int ans=0; 12 13 int is_prime(intx){ 14 for( int i=2; i*i<=x; i++){ 15 if(x%i==0) return 0; 16 } 17 return 1; 18 } 19 20 void dfs(intcur){ 21 if(cur==n&&isp[A[0]+A[n-1]]){ 22 ans++; 23 for( int i=0; i<n; i++ ) cout<<A[i]<<" "; 24 cout<<endl; 25 } 26 else{ 27 for(int i=2; i<=n; i++){ 28 if(!vis[i]&&isp[i+A[cur-1]]){/*i这个数没被用过，并且符合前后两个数相加为素数的要求*/ 29 A[cur]=i;/*采用这个数*/ 30 vis[i]=1;/*设置使用标志*/ 31 dfs(cur+1); 32 vis[i]=0;/*消除标志*//*回溯的本质*/ 33 } 34 } 35 } 36 } 37 int main(int argc, char const *argv[]) 38 { 39 cin>>n; 40 memset(vis,0,sizeof(vis)); 41 for( int i=2; i<=n*2; i++ ) isp[i]=is_prime(i); 42 A[0]=1;/*题目中规定从1开始*/ 43 dfs(1); 44 cout<<ans<<endl; 45 46 return 0; 47 }