2012第四届湘潭市大学生程序设计竞赛A题

Anti-Goldbach's Conjecture

哥德巴赫猜想：

任一大于2的偶数，都可表示成两个素数之和。

是世界上最著名的未解问题之一，但是下面的反哥德巴赫猜想：

任一大于11的奇数，都可表示成两个合数之和。

确很容易证明。

定义反哥德巴赫分拆数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

13

14

15

Sample Output

1

1

2

 

由题目意思可得:

 

sg[n]=sg[n-2]+g[n]; （1）非常明显可以得到

 g[n]=g[n-2]+;  （2）//composite[n]表示n是否为素数

 解释一下等式（2）。因为g[n-2]是奇数，对于它的任何一个有效分解都是奇数X和偶数Y（Y>=4），X和Y+2（Y+2必然是合数）必然是g[n]的一个有效分解。而(n-4,2)必然不是g[n-2]的分解，但是数对(n-4,4)可能是g[n]的有效分解，所以引入composite[]数组。

很显然，我们首先可以算出数组composite，然后利用式（2）(1)计算出g[]和sg[]

#include
#include
#include
#include
using namespace std;

#ifdef  _MSC_VER
typedef __int64 LL;
#else
typedef long long LL;
#endif


const int MAXN=1<<20;
int composite[MAXN];//是否合数数组
LL sg[MAXN];

int main()
{
    int i,n;
   
   
     for(i=2;i        if(!composite[i]){
            for(int j=i+i;j                composite[j]=1;
        }
    }
    sg[11]=0;
    int g=0; //g代表g(n)
    for(i=13;i        g+=composite[i-4];
        sg[i]=sg[i-2]+g;
    }

    while(~scanf("%d",&n)){
        printf("%lld\n", n%2?sg[n]:sg[n-1]);
    }
    return 0;
}