POJ 2262 Goldbach's Conjecture( 素數相關)

http://poj.org/problem?id=2262

題意：

?????? 給你一個[6,1000000]范圍內的偶數，要你將它表示成兩個素數相加和的形式。假設存在多組解，請輸出兩個素數差值最大的解。

分析：

?????? 首先我們用素數篩選法求出100W以內的全部素數。

?????? 篩選法求素數可見：

?????? http://blog.csdn.net/u013480600/article/details/41120083

?????? 對于給定的數X，假設存在素數a+素數b==X且a與b的差距最大。那么一定僅僅須要從小到大枚舉素數a即可，然后用X-a就是b。再推斷b是否是素數即可。（ 想想是不是 ）

AC 代碼：

      #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000000;

//素數篩選法
bool not_prime[maxn+5];//not_prime[i]=true表i不是素數
int prime[maxn+5];
int get_prime()
{
    memset(prime,0,sizeof(prime));
    //注意：not_prime[i]=false時，i為素數
    memset(not_prime,0,sizeof(not_prime));

    for(int i=2;i<=maxn;i++)
    {
        if(!not_prime[i]) prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++)
        {
            not_prime[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
    return prime[0];
}

int main()
{
    //生成100W以內全部素數
    get_prime();

    int x;
    while(scanf("%d",&x)==1 && x)
    {
        int a,b;//x被拆分為a和b兩個數
        bool ok=false;
        for(int i=1;i<=prime[0] && prime[i]<=x/2;i++)
        {
            a=prime[i];
            b=x-a;
            if(!not_prime[b])//若b是素數
            {
                ok=true;
                break;
            }
        }
        if(ok) printf("%d = %d + %d\n",x,a,b);
        else printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}