/* 此法為判斷素?cái)?shù) 和 篩法球素?cái)?shù)*/
# include<stdio.h>
# include<math.h>
# include<string.h>
const int maxn = 30;
int n;
int primer[maxn];
void myPrimer1(int n)//計(jì)算 1- n 之間的素?cái)?shù)我們知道，合數(shù)都可以分解成若干質(zhì)數(shù)，所以只要2~sqrt(i)間的質(zhì)數(shù)不能整除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 小的素?cái)?shù)最大下標(biāo)
for (j=0; j<stop; j++)
if (i%primer[j] == 0) break;// i不能被2~sqrt(i)間的素?cái)?shù)整除，自然也不能被其他數(shù)整除,素?cái)?shù)也
if(j == stop)
primer[count ++] = i;
}
}
int isp[maxn]; //構(gòu)造素?cái)?shù)表 0 表示不是 1 表示是
void myPrimer2(int n)
{
int i,j;
int count ;
isp[2] = 1;
for(i = 3; i < n; i ++ )
{
isp[i] =1;//先將奇數(shù)置為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)//轉(zhuǎn)承法為加法
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
付翔 閱讀(534)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM 數(shù)據(jù)結(jié)構(gòu)