poj 2909 Goldbach's Conjecture

用素数筛法筛一次,然后验算下就OK
#include <stdio.h>
#include 
<string.h>

int t[33000], prime[3000], p= 0;
int m, count;

void init()
{
    memset (t, 
0sizeof(t));
    
for ( int i = 2 ; i < 33000 ; i++ )
    {
        
if!t[i] )
        {
            prime[p
++]= i;
            
for ( int j = i*2; j < 33000 ; j += i )
                t[j]
= 1;
        }
    }
}

int main()
{
    init();
    
while ( scanf("%d"&m), m )
    {
        count
=0;
        
int mid= m>>1;
        
int i, j, a;
        
for ( i = 0; prime[i] <= mid; i++ )
        {
            a
= prime[i];
            
if ( !t[m-a] )
                count
++;
        }
        printf(
"%d\n", count);
    }
    
return 0;
}

posted on 2011-08-17 00:41 purplest 阅读(169) 评论(0)  编辑 收藏 引用 所属分类: 枚举


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


<2011年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

常用链接

留言簿

随笔分类(70)

随笔档案(68)

ACMer

搜索

最新随笔

最新评论