/* 此法为判断素数 和 筛法球素数*/
# include<stdio.h>
# include<math.h>
# include<string.h>
const int maxn = 30;
int n;
int primer[maxn];
void myPrimer1(int n)//计算 1- n 之间的素数我们知道，合数都可以分解成若干质数，所以只要2~sqrt(i)间的质数不能整除i即可
{
int i,j,k,stop;
int count = 0;
primer[count ++] = 2;
stop = count;
for(i = 3; i <= n; i ++)
{
k = (int)sqrt(i*1.0);
while (primer[stop] <= k && stop < count)
stop++;// 获取比k 小的素数最大下标
for (j=0; j<stop; j++)
if (i%primer[j] == 0) break;// i不能被2~sqrt(i)间的素数整除，自然也不能被其他数整除,素数也
if(j == stop)
primer[count ++] = i;
}
}
int isp[maxn]; //构造素数表 0 表示不是 1 表示是
void myPrimer2(int n)
{
int i,j;
int count ;
isp[2] = 1;
for(i = 3; i < n; i ++ )
{
isp[i] =1;//先将奇数置为1
isp[++i] = 0;
}
if(n%2!= 0)
isp[n] = 1;
for(i = 3; i <= n/2; i ++)
{
if(0 == isp[i]) continue;
for (j=i+i; j <= n; j+=i)//转承法为加法
isp[j] = 0;
}
}
int A[maxn] ,visted[maxn];
void dfs(int cur)
{
if(cur == n && isp[A[0] + A[n-1]] ==1 )
{
for(int i = 0; i < n; i ++) printf(i==0 ?"%d":" %d",A[i]);
printf("\n");
}
else
{
for(int i = 2; i <= n; i ++)
{
if(visted[i] == 0 && isp[i + A[cur-1]] == 1)
{
visted[i] = 1;// 此为精妙之处
A[cur] = i;
dfs(cur +1);
visted[i] = 0;// 此为精妙之处
}
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
// freopen("out2.txt","w",stdout);
int caseId = 1;;
myPrimer2(42);
/*for(i = 0; i < 200; i ++)
{
printf("%d : %d ;",i,isp[i]);
if(i %10 ==0)printf("\n");
}*/
while(scanf("%d",&n)!=EOF)
{
memset(visted,0,sizeof(visted));
memset(A,0,sizeof(A));
A[0] = 1;
printf("Case %d:\n",caseId++);
dfs(1);
printf("\n");
}
return 0;
}
posted on 2010-05-21 16:02
付翔 阅读(497)
评论(0) 编辑 收藏 引用 所属分类:
ACM 数据结构