心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
rqnoj 131 哥德巴赫猜想(Easy)

练习了一下筛素数。

以下是我的代码：

#include<stdio.h>
long n,tot,prime[10000];
bool isprime[100008];
void init()
{
    for(long i=1;i<=n;i++)
      isprime[i]=true;
    tot=0;
    isprime[1]=false;
    for(long i=2;i<=n;i++)
    {
       if(isprime[i])
       {
          tot++;
          prime[tot]=i;
       }
       for(long j=1;j<=tot&&i*prime[j]<=n;j++)
       {
          isprime[i*prime[j]]=false;
          if(i%prime[j]==0) break;
       }
    }
    //for(long i=1;i<=tot;i++) printf("%ld ",prime[i]);putchar('\n');
}
bool PrimeOk(long x)
{
    if(x==1) return false;
    if(x==2) return true;
    for(long i=1;i<=tot&&prime[i]<x;i++)
      if(x%prime[i]==0)
        return false;
    return true;
}
void work()
{
    for(long i=4;i<=n;i+=2)
    {
       for(long j=1;j<=tot&&prime[j]<i;j++)
       {
          long t=i-prime[j];
          if(PrimeOk(t))
          {
             printf("%ld=%ld+%ld\n",i,prime[j],t);
             break;
          }
       }
    }
}
int main()
{
    scanf("%ld",&n);
    init();
    work();
return 0;
}
posted on 2010-01-06 20:36 lee1r 阅读(144) 评论(0)  编辑 收藏 引用 所属分类: 题目分类：数学/数论

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


Copyright ©2024 lee1r Powered By博客园 模板提供：沪江博客