付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0
/* 此法为判断素数 和 筛法球素数*/

# 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] == 0break;// 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 付翔 阅读(496) 评论(0)  编辑 收藏 引用 所属分类: ACM 数据结构

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2010年5月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜