poj 2909 Goldbach's Conjecture （哥德巴赫猜想）
水题
写一遍的目的是。。。复习一下快速筛的写法 喵呜
/*************************************************************************
> File Name: code/poj/2909.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年08月22日 星期六 14时25分34秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#define y0 abc111qqz
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define tm crazy111qqz
18#define lr dying111qqz
19using namespace std;
20#define REP(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef unsigned long long ULL;
23const int inf = 0x3f3f3f3f;
24const int N=1<<16;
25bool not_prime[N];
26int prime[N];
27int prime_num;
28int n;
1void init(){
2 not_prime[0] = true;
3 not_prime[1] = true;
4 for ( int i =2 ; i < N ; i++){
5 if (!not_prime[i]){
6 prime[++prime_num] = i;
7 }
8 for ( int j = 1 ; j <= prime_num&&i*prime[j]<N ; j++){
9 not_prime[i*prime[j]] = true;
10 if (i%prime[j]==0) break;
11 }
12 }
13}
14int main()
15{
16 init();
17 int n ;
18 while (scanf("%d",&n)&&n){
19 int ans = 0 ;
20 for ( int i = 2 ; i <= n /2 ; i++){
21 if (!not_prime[i]&&!not_prime[n-i]){
22 ans++;
23 }
24 }
25 printf("%d\n",ans);
26 }
return 0;
}