2262.cpp

北京大学ACM比赛题目 In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard

#include"stdio.h"
#include"string.h"
#include"math.h"
#define M 1000001
int main()
{
    int N;
    int p;
    int i,j,k=0;
    int jishu1;
    bool zhishu[M]={0};
    zhishu[0]=1;
    zhishu[1]=1;
    for(i=2;i<M/2;i++){
        if(zhishu[i]==0){
            for(j=2;j*i<M;j++)
                zhishu[i*j]=1;
        }    
    }
    while(1){
        scanf("%d",&N);
        if(N==0) break;
        jishu1=0;
        for(i=2;i<=N/2;i++){
          if(i>3) i++;                  
          if(zhishu[i]==0){
             p=N-i;
             if(zhishu[p]==0){
                 jishu1=1;
                 break;
             }
          }
        }
        if(jishu1==1) printf("%d = %d + %d\n",N,i,p);
        else printf("Goldbach's conjecture is wrong.\n");
    }
return 0;
}