/* 此法為判斷素數 和 篩法球素數*/
# 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
付翔 閱讀(516)
評論(0) 編輯 收藏 引用 所屬分類:
ACM 數據結構