2014
03-30

# Goldbach Division

Everybody knows Goldbach Conjecture! Here is one edition of it:

1) Every odd integer greater than 17 can be written as three different odd primes’ sum;
2) Every even integer greater than 6 can be written as two different odd primes’ sum.

Loving the magical math conjecture very much, iSea try to have a closer look on it. Now he has a new definition: Goldbach Division. If we express an even integer as two different odd primes’ sum, or odd integer as three different odd primes’ sum, we call it a form of Goldbach Division of N, using a symbol G(N).

For example, if N = 18, there are two ways to divide N.
18 = 5 + 13 = 7 + 11
If N = 19, there is only one way to divide N.
19 = 3 + 5 + 11

Here comes your task, give a integer N, find |G(N)|, the number of different G(N).

There are several test cases in the input.

Each test case includes one integer N (1 <= N <= 20000).

The input terminates by end of file marker.

There are several test cases in the input.

Each test case includes one integer N (1 <= N <= 20000).

The input terminates by end of file marker.

18
19

2
1
HintThere may be 2000 cases, be careful. 

#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;

int prime[3000],num;
int ans[20010];

void init()
{
bool succ[20010];
num=0;
memset(succ,0,sizeof(succ));
for (int i=2;i<=20000;i++)
if (!succ[i])
{
prime[num++]=i;
for (int j=i*i;j<=20000;j+=i)
succ[j]=true;
}
memset(ans,0,sizeof(ans));
for (int i=1;i<num;i++)
for (int j=i+1;j<num&&(prime[i]+prime[j]<=20000);j++)
ans[prime[i]+prime[j]]++;

for (int i=6;i<=20000;i+=2)
for (int j=1;j<num&&(i+prime[j]<20000);j++)
ans[prime[j]+i]+=ans[i];

for (int i=1;i<num&&(2*prime[i]<20000);i++)
for (int j=1;j<num&&(2*prime[i]+prime[j]<20000);j++)
if (j!=i)
ans[2*prime[i]+prime[j]]--;

for (int i=3;i<=20000;i+=2)
ans[i]/=3;
}

int main()
{
init();
int n;
while(scanf("%d",&n)!=EOF)
{
printf("%d\n",ans[n]);
}
return 0;
}

1. 站长好。我是一个准备创业的互联网小白,我们打算做一个有关国*际*游*学的平台。手上也有了一些境外资源。现阶段的团队现在没有cto.原意出让一些管理股寻找一个靠谱的技术专家做合伙人, 不知道是不是能得到您的帮助。发个帖子或者其他方式。期待您的回应。可以加我微信tianxielemon聊聊。