湘潭市邀请赛A

湘潭邀请赛A
哥德巴赫猜想：

定义反哥德巴赫分拆数g(n)表示将大于11的奇数n分解为两个合数之和的方案数。再定义sg(n)=sum({g(i) | i ≤ n})，即所有不大于n的奇数的反哥德巴赫分拆数之和。你的任务就是快速的计算给定n所对应的sg(n)。

Input

有大约100组测试数据。每组测试数据占一行，包含唯一的一个正整数13 ≤ n ≤ 1000000。输入以EOF结束。

Output对于输入n，输出对应的sg(n)。

Sample Input

131415

Sample Output

112

水题，代码：

#include <cstdio>#include <algorithm>using namespace std;const int MAXN = 1 << 20;bool p[MAXN];vector<int> odd, even;int main() {    for (int i = 2; i < MAXN; ++i) {        if (!p[i]) {            for (int j = i + i; j < MAXN; j += i) {                p[j] = true;            }        } else if (i % 2 != 0) {            odd.push_back(i);        } else {            even.push_back(i);        }    }    int n;    while (scanf("%d", &n) != EOF) {        int i = 0, j = lower_bound(even.begin(), even.end(), n) - even.begin();        long long m = 0;        while (i < (int)odd.size() && j >= 0) {            while (j >= 0 && odd[i] + even[j] > n) {                --j;            }            ++i;            m += j + 1;        }        printf("%lld\n", m);    }    return 0;}