POJ 2262 Goldbach's Conjecture( 素?cái)?shù)相關(guān))

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

題意：

?????? 給你一個(gè)[6,1000000]范圍內(nèi)的偶數(shù)，要你將它表示成兩個(gè)素?cái)?shù)相加和的形式。假設(shè)存在多組解，請(qǐng)輸出兩個(gè)素?cái)?shù)差值最大的解。

分析：

?????? 首先我們用素?cái)?shù)篩選法求出100W以內(nèi)的全部素?cái)?shù)。

?????? 篩選法求素?cái)?shù)可見：

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

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

AC 代碼：

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

//素?cái)?shù)篩選法
bool not_prime[maxn+5];//not_prime[i]=true表i不是素?cái)?shù)
int prime[maxn+5];
int get_prime()
{
    memset(prime,0,sizeof(prime));
    //注意：not_prime[i]=false時(shí)，i為素?cái)?shù)
    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以內(nèi)全部素?cái)?shù)
    get_prime();

    int x;
    while(scanf("%d",&x)==1 && x)
    {
        int a,b;//x被拆分為a和b兩個(gè)數(shù)
        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是素?cái)?shù)
            {
                ok=true;
                break;
            }
        }
        if(ok) printf("%d = %d + %d\n",x,a,b);
        else printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}