哥德巴赫猜想：任何一個大于2的偶數(shù)，都可以表示為兩個素數(shù)之和。

?

另外還有，任何一個大于5的奇數(shù)都可以表示為三個素數(shù)之和。

?

?

題目：http://acm.timus.ru/problem.aspx?space=1&num=1356

?

題意：給定一個正整數(shù)n，范圍是[2,10^9]，把n表示為若干個素數(shù)的和，輸出一種方案，使得素數(shù)的個數(shù)最少。

?

分析：如果n是素數(shù)，那么直接輸出它即可；

???? 否則如果n是大于2的偶數(shù)，那么根據(jù)哥德巴赫猜想它可以表示為兩個素數(shù)之和，可以用Miller_Rabin判斷；

???? 否則，n就只能是奇數(shù)且非素數(shù)，那么對于任意一個大于5的奇數(shù)，我們先判斷它是否是2和一個素數(shù)的和，即判斷n-2是

???? 否是素數(shù)，如果是，那么就可以表示為兩個素數(shù)相加

???? 否則我們可以把它表示為3個素數(shù)之和。n-3+3=n，注意3是素數(shù)，而且n-3是偶數(shù)，這樣我們可以把n表示n=p1+p2+3.

?

所以經(jīng)過上面的分析，對于任意一個正整數(shù)n，我們最多可以用3個素數(shù)之和來表示它。

?

一般來說，對于一個大于2偶數(shù)n，范圍在[4,10^9]，表示為兩個素數(shù)之和后，小的那個素數(shù)不會很大，所以我們可以在區(qū)間

[2,100000]里面枚舉素數(shù)就可以了。

?

?

?

題目描述：哥德巴赫猜想認為任一大于2的偶數(shù)，都可表示成兩個素數(shù)之和，比如

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以內(nèi)的偶數(shù)，將它表示為素數(shù)的和有幾種方式？(結(jié)果對10^9+7取模)

?

分析：相當于求以質(zhì)數(shù)為物品體積，背包容量為10000的，可以重復(fù)選擇的背包，設(shè)p[i]是第i個質(zhì)數(shù)，dp[i][n]表示把正整

數(shù)n拆分為不大于p[i]的若干質(zhì)數(shù)和的方案數(shù)，則有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; }

?

?

總結(jié)

以上是生活随笔為你收集整理的哥德巴赫猜想的拓展的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。