首页 > 代码库 > nyist 488 素数环
nyist 488 素数环
素数环
- 描述
有一个整数n，把从1到n的数字无重复的排列成环，且使每相邻两个数（包括首尾）的和都为素数，称为素数环。
为了简便起见，我们规定每个素数环都从1开始。例如，下图就是6的一个素数环。
- 输入
- 有多组测试数据，每组输入一个n(0<n<20)，n=0表示输入结束。
- 输出
- 每组第一行输出对应的Case序号，从1开始。 如果存在满足题意叙述的素数环，从小到大输出。 否则输出No Answer。
- 样例输入
6830
- 样例输出
Case 1:1 4 3 2 5 61 6 5 2 3 4Case 2:1 2 3 8 5 6 7 41 2 5 8 3 4 7 61 4 7 6 5 8 3 21 6 7 4 3 8 5 2Case 3:No Answer
*****************************************************************************************************************************************
TimeLimitExceeded
View Code#include <stdio.h>#include<cstring>int a[30],n,used[40];int is_prime(int x){ for(int i=2;i<x; i++) if(x%i==0) return 0; return 1; }void dfs(int cur){ int i; if(cur==n && is_prime(a[n]+a[1])) { for(i=1;i<n;i++) printf("%d ",a[i]); printf("%d\n",a[n]); return; } for(i=2;i<=n;i++) { if(used[i]==0 && is_prime(a[cur]+i)) { a[cur+1]=i ; used[i]=1 ; dfs(cur+1);used[i]=0 ;} } } main( ){ int c=1; while(scanf("%d",&n)!=EOF) { memset(used,0,sizeof(used)) ; a[1]=1; used[1]=1; printf("Case %d:\n",c++); dfs(1); //cout<<endl; if(n==1) printf("") ; else if(n%2) printf("No Answer\n"); else if(n==0) break; } }8888888888888888888888888888#include <iostream>#include<cstring>using namespace std;int a[30],n,used[40];int is_prime(int x){ for(int i=2;i<x; i++) if(x%i==0) return 0; return 1; }void dfs(int cur){ int i; if(cur==n && is_prime(a[n]+a[1])) { for(i=1;i<n;i++) cout<<a[i]<<" "; cout<<a[n]<<"\n"; return; } for(i=2;i<=n;i++) { if(used[i]==0 && is_prime(a[cur]+i)) { a[cur+1]=i ; used[i]=1 ; dfs(cur+1);used[i]=0 ;} } } main( ){ int c=1; while(cin>>n) { memset(used,0,sizeof(used)) ; a[1]=1; used[1]=1; cout<<"Case "<<c++<<":"<<endl ; dfs(1); //cout<<endl; if(n==1) cout<<"" ; else if(n%2) cout<<"No Answer"<<endl; else if(n==0) break; } }
******************************************************************************************************************************************View Code#include <iostream>#include <string.h>using namespace std;int a[30],used[30];int n;int is_prime( int x){for (int i=2; i<x; i++) if (x%i==0) return 0;return 1;}void dfs(int cur){ int i;if (cur==n && is_prime ( a[1]+a[n] )){ for (i=1; i<n; i++ ) cout<<a[i]<<" ";cout<<a[n]<<"\n";return ; }for (i=2; i<=n;i++){ if ( used[i]==0 && is_prime ( a[cur]+i ) ) { a[cur+1]=i ; used[i]=1; dfs(cur+1); used[i]=0; }}}int main( ){ int c=1;while (cin>>n,n){ memset(used,0,sizeof(used));a[1]=1; used[1]=1;cout<<"Case "<<c++<<":\n";if (n%2==0) dfs(1);else if (n==1) cout<<"1\n";else cout<<"No Answer\n"; cout<<endl;}return 0;}
#include <iostream>
#include <string.h>
using namespace std;
int a[30],used[30];
int n;
int is_prime( int x)
{ for (int i=2; i<x; i++)
if (x%i==0) return 0;
return 1; }
void dfs(int cur)
{ int i;
if (cur==n && is_prime ( a[1]+a[n] ))
{ for (i=1; i<n; i++ )
cout<<a[i]<<" "; cout<<a[n]<<"\n"; return ;
}
for (i=2; i<=n;i++)
{
if ( used[i]==0 && is_prime ( a[cur]+i ) )
{ a[cur+1]=i ; used[i]=1; dfs(cur+1); used[i]=0; }
}
}
int main( )
{
int c=1;
while (cin>>n,n)
{
memset(used,0,sizeof(used));
a[1]=1; used[1]=1;
cout<<"Case "<<c++<<":\n";
if (n%2==0) dfs(1);
else if (n==1) cout<<"1\n";
else cout<<"No Answer\n";
cout<<endl;
}
return 0;
}
View Code#include<stdio.h>#include<stdlib.h>int prime[12]={2,3,5,7,11,13,17,19,23,29,31,37};int p[30],used[30],n;int IsPrime(int num){ int j; for (j=0;j<12;j++) if (num==prime[j]) return 1; return 0;}void DFS(int i){ int j; if (i==n&&IsPrime(p[n]+p[1])) { for (j=1;j<n;j++) printf("%d ",p[j]); printf("%d\n",p[j]); return; } for (j=2;j<=n;j++) { if ( used[j]==0 && IsPrime(p[i]+j) ) { p[i+1]=j; used[j]=1; DFS(i+1); used[j]=0; } }}int main(){ int i=1,j; while (scanf("%d",&n) && n ) { for (j=0;j<30;j++) used[j]=0; printf("Case %d:\n",i++); p[1]=1; if (n%2==0 || n==1) DFS(1); else printf("No Answer\n"); } return 0;}
#include<stdio.h>
#include<stdlib.h>
int prime[12]={2,3,5,7,11,13,17,19,23,29,31,37};
int p[30],used[30],n;
int IsPrime(int num)
{
int j;
for (j=0;j<12;j++)
if (num==prime[j]) return 1;
return 0;
}
void DFS(int i)
{
int j;
if (i==n&&IsPrime(p[n]+p[1]))
{
for (j=1;j<n;j++) printf("%d ",p[j]);
printf("%d\n",p[j]);
return;
}
for (j=2;j<=n;j++)
{ if ( used[j]==0 && IsPrime(p[i]+j) )
{ p[i+1]=j; used[j]=1; DFS(i+1); used[j]=0; }
}
}
int main()
{
int i=1,j;
while (scanf("%d",&n) && n )
{
for (j=0;j<30;j++) used[j]=0;
printf("Case %d:\n",i++); p[1]=1;
if (n%2==0 || n==1) DFS(1);
else printf("No Answer\n");
}
return 0;
}
