POJ 2262 Goldbach's Conjecture

这篇博客是从旧博客 WordPress 迁移过来，内容可能存在转换异常。

大家都说是水题，可能是自己实力差把，我感觉可不水。

我用普通的判断sqrt(n)的方法求素数，结果TLE了。

看了论坛一个朋友的方法，是用的筛选法。

 #include 
#include 
#include 
using namespace std;

/*
bool Is_odd_prime(int n)
{
    int i;
    if(n % 2 == 0)
        return 0;
    for(i = 2; i < sqrt(double(n)); i++)
        if(n % i == 0)
            return 0;
    if(i == n/2)
        return 1;
}
*/


int prime[1000000];


int main()
{
    int i, j;
    memset(prime, 1, sizeof(prime));
    for(i = 2; i < 1000; i++)
        if(prime[i])
            for(j = i*2; j < 1000000; j+=i)
                prime[j] = 0;

    int n;
    while(scanf("%d", &n;) && n != 0)
    {
        int i;
        for(i = 2; i <= n/2; i++)
            if(prime[i] && prime[n-i])
            {
                printf("%d = %d + %d\n", n, i, n-i);
                break;
            }
        if(i == n/2+1)
            printf("Goldbach's conjecture is wrong.\n");
    }
    return 0;
}