題目描述

本題為填空題，只需要算出結果后，在代碼中使用輸出語句將所填結果輸出即可。

將?2019 拆分為若干個兩兩不同的質數之和，一共有多少種不同的方法？

注意交換順序視為同一種方法，例如?2+2017=2019 與?2017+2=2019 視為同一種方法。

方法：動態規劃（0-1背包問題）

這個問題可以轉化為?0-1背包問題：

• 背包容量?=?2019

• 物品?= 所有小于?2019?的質數（每個質數只能選或不選）

• 目標：求恰好裝滿背包的組合數

#include<iostream>
#include<cmath>
using namespace std;#define int long long int a[2020];
int dp[2020];  //dp[j]表示和為j的組合數 bool prime(int x)
{if(x<2) return 0;if(x==2) return 1;for(int i=2; i<=sqrt(x); ++i){if(x%i==0) return 0;}return 1;
}signed main()
{int cnt = 0;  //記錄質數的數量 for(int i=2; i<=2019; ++i){if(prime(i)){a[cnt] = i;cnt++;}}dp[0] = 1;  //初始條件：和為0的組合數為1for(int i=0; i<cnt; ++i){for(int j=2019; j>=a[i]; j--){dp[j] += dp[j - a[i]];} }cout<<dp[2019];return 0;
}