斑的家

//============================================================================
// Name        : 10311.cpp
// Author      : benbendog
// DATE        : 2010/12/12
// Version     :
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
/*
 * PROBLEM : GoldBach conjecture, determine if a number is the sum
 *           of 2 primes, and diff of 2 primes > 0
 * SOLUTION: the range is very big 0~10^8
 *           first, find the prime in [0,10^4]
 *           then given a number if it is odd ,
 *           it can only be 2 + n-2, if n-2 is not prime, done
 *           if the number is even
 *           test i=[ n/2 ~ 3], test isPrime(i) & isprime(n-i).
 */
#include <iostream>
#include <cmath>
#define RANGE 100000001
#define SIZE 10001
using namespace std;
bool s[RANGE];
int f[SIZE];
int cnt;
void init();
bool isPrime(int n);
int main() {
    int n,i;
    init();
    while(cin>>n)
    {
        // odd number
        if(n&1)
        {
            if(n <= 3)
            {
                printf("%d is not the sum of two primes!\n",n);
                continue;
            }
            if(isPrime(n-2))
                printf("%d is the sum of 2 and %d.\n",n,n-2);
            else
                printf("%d is not the sum of two primes!\n",n);
        }
        else
        {
            i = n>>1;
            if(!(i&1))i--;
            for(; i >2 ; i-=2)
            {
                if(isPrime(i) && isPrime(n-i) && n-i!=i)
                {
                    printf("%d is the sum of %d and %d.\n",n,i,n-i);
                    break;
                }
            }
            if(i<2)
            printf("%d is not the sum of two primes!\n",n);
        }
    }
    return 0;
}
void init()
{
    cnt = 0;
    memset(s,true,sizeof(s));
    for(int i =2 ; i <SIZE;i++ )
    {
        if(!s[i])continue;
        f[cnt++]=i;
        for(int j =2*i ; j<SIZE;j+=i)
            f[j] = false;
    }
}
bool isPrime(int n)
{
    // suppose n > 2 , n is odd
    int sq = sqrt(n),i;
    for(i = 3 ;i <=sq ;i+=2)
        if(n%i==0)return false;
    return true;
}