哥德巴赫猜想的拓展
哥德巴赫猜想：任何一个大于2的偶数，都可以表示为两个素数之和。
另外还有，任何一个大于5的奇数都可以表示为三个素数之和。
题目：http://acm.timus.ru/problem.aspx?space=1&num=1356
题意：给定一个正整数n，范围是[2,10^9]，把n表示为若干个素数的和，输出一种方案，使得素数的个数最少。
分析：如果n是素数，那么直接输出它即可；
否则如果n是大于2的偶数，那么根据哥德巴赫猜想它可以表示为两个素数之和，可以用Miller_Rabin判断；
否则，n就只能是奇数且非素数，那么对于任意一个大于5的奇数，我们先判断它是否是2和一个素数的和，即判断n-2是
否是素数，如果是，那么就可以表示为两个素数相加
否则我们可以把它表示为3个素数之和。n-3+3=n，注意3是素数，而且n-3是偶数，这样我们可以把n表示n=p1+p2+3.
所以经过上面的分析，对于任意一个正整数n，我们最多可以用3个素数之和来表示它。
一般来说，对于一个大于2偶数n，范围在[4,10^9]，表示为两个素数之和后，小的那个素数不会很大，所以我们可以在区间
[2,100000]里面枚举素数就可以了。
题目描述：哥德巴赫猜想认为任一大于2的偶数，都可表示成两个素数之和，比如
6 = 2+2+2
6 = 3+3
10 = 2+2+2+2+2
10 = 2+2+3+3
10 = 2+3+5
10 = 3+7
像3+7与7+3只有顺序不一样的认为是一种方式
问：给定一个10000以内的偶数，将它表示为素数的和有几种方式？(结果对10^9+7取模)
分析：相当于求以质数为物品体积，背包容量为10000的，可以重复选择的背包，设p[i]是第i个质数，dp[i][n]表示把正整
数n拆分为不大于p[i]的若干质数和的方案数，则有dp[i][n]=dp[i-1][n]+dp[i][n-p[i]]
#include <iostream>#include <string.h>#include <stdio.h>#include <vector>using namespace std;typedef long long LL;const int N = 10005;const LL MOD = 1000000007;bool prime[N];int p[N];int k;vector<LL> v1;vector<LL> v2;vector<LL> *p1;vector<LL> *p2;void isprime(){ k = 0; int i,j; memset(prime,true,sizeof(prime)); for(i=2;i<N;i++) { if(prime[i]) { p[k++] = i; for(j=i+i;j<N;j+=i) { prime[j] = false; } } }}void Work(){ p1 = &v1; p2 = &v2; for(int i=0;i<N;i++) { if(i&1) p1->push_back(0); else p1->push_back(1); } for(int i=1;i<k;i++) { p2->clear(); for(int j=0;j<N;j++) { if(j < p[i]) p2->push_back((*p1)[j]%MOD); else p2->push_back(((*p1)[j]%MOD + (*p2)[j-p[i]]%MOD)%MOD); } vector<LL> *tmp; tmp = p2; p2 = p1; p1 = tmp; }}int main(){ int n; isprime(); Work(); while(cin>>n) { cout<<(*p1)[n]<<endl; } return 0;}