POJ 2262 Goldbach's Conjecture 数学常识 难度:0

题目链接:http://poj.org/problem?id=2262

哥德巴赫猜想肯定是正确的

思路:

　　筛出n范围内的所有奇质数,对每组数据试过一遍即可,

　　为满足b-a取最大,a取最小

时空复杂度分析:

　　在1e6内约有8e4个奇质数,因为a <= b,时间复杂度在T*4e4+1e6等级.一般T为1e3,足以承受

　　空间复杂度为1e6,足以承受

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 6;
int n;
bool ntp[maxn];
int prime[maxn],cnt;
void judgeprime()
{
    for(int i = 3;i < maxn;i += 2)
    {
        if(ntp[i])continue;
        prime[cnt++] = i;
        for(int j = 3;j * i < maxn;j += 2)
        {
            ntp[i * j] = true;
        }
    }

}

int main()
{
    judgeprime();
    while(scanf("%d",&n)==1 && n)
    {
        for(int i = 0;i < cnt && i < n / 2;i++)
        {
            if(!ntp[n - prime[i]])
            {
                printf("%d = %d + %d
",cnt,prime[i],n - prime[i]);
                break;
            }
        }
    }
    return 0;
}