1397b goldbach's conjecture.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

/*
1397 Goldbach's Conjecture
Time Limit : 1000 ms  Memory Limit : 32768 K  Output Limit : 256 K

968 MS 316 KB 1438 B
GUN C++
*/
//用筛法
#include <iostream>
#include <cstdio>
using namespace std;

const int Max=32769;

/************筛选法求素数_改进***************/
int sievePrime_2(int savenum[],int n)
{
    int ca,temp,now;
    int num[Max]={0};
    savenum[0]=2;now=1;

    for(ca=3;ca<=n;ca+=2)
    {
        if(num[(ca-1)/2]==0)
        {
            temp=ca+ca;
            while(temp<=n)
            {
                if(temp%2!=0)
                    num[(temp-1)/2]=1;
                temp+=ca;
            }
        }
    }

    for(ca=3;ca<=n;ca+=2)
        if(num[(ca-1)/2]==0)
        {   savenum[now]=ca;now++;}

    return now-1;
}

int divFind(int num[],int findnum,int size)
{
    int low=0,high=size,mid;
    while(high-low>=0)
    {
        mid=(low+high)/2;
        if(num[mid]==findnum)
            return mid;
        else
        {
            if(num[mid]>findnum)
            {   high=mid-1;}
            else
            {   low=mid+1;}
        }
    }
    return -1;
}

int main()
{
    int n,i,temp,count,ca;
    int prime[3600],size;

    size=sievePrime_2(prime,Max);
    
    while(scanf("%d",&n) && n!=0)
    {
        temp=n/2;
        count=0;
        for(i=0;i<=size;i++)//防止重复的计算
            if(prime[i]>=temp)
                break;

        if(prime[i]==temp)//相等时，是一种答案
            count++;

        for(ca=0;ca<i;ca++)
        {
            if(divFind(prime,n-prime[ca],size)>0)
                count++;
        }
        printf("%d\n",count);
    }
    return 0;
}