問題描述】

2019可以被分解成若干個兩兩不同的素數，請問不同的分解方案有多少種？ 注意：分解方案不考慮順序，如 2 + 2017 = 2019 和 2017 + 2 = 2019 屬于同一種方案。

答案：55965365465060

代碼如下：

#include <iostream> using namespace std; const int N = 2500;//空間要開大一點 long long dp[N][N]; int p[N]; bool vis[N]; int k = 1;void is_prime() {for (int i = 2;i<=2019;i++){if (!vis[i])for (int j = i*i;j<=2019;j+=i) vis[j] = true;}for (int i = 2;i<=2019;i++) {if (!vis[i]) p[k++] = i;} }int main() {is_prime();dp[0][0] = 1;for (int i = 1;i<k;i++)for (int j = 0;j<=2019;j++){dp[i][j] = dp[i-1][j];if (j >= p[i]) dp[i][j]+=dp[i-1][j-p[i]];}cout<<dp[k-1][2019]<<endl;return 0; }

空間優化：

#include <iostream> using namespace std; const int N = 2500; long long dp[N]; bool vis[N]; int p[N]; int k = 1; void is_prime() {for (int i = 2;i<=2019;i++){if (!vis[i])for (int j = i*i;j<=2019;j+=i) vis[j] = true;}for (int i = 2;i<=2019;i++){if (!vis[i]) p[k++] = i;} }int main() {is_prime();dp[0] = 1;for (int i = 1;i<k;i++)for (int j = 2019;j>=p[i];j--){dp[j] += dp[j-p[i]];}cout<<dp[2019]<<endl;return 0; }

總結

以上是生活随笔為你收集整理的2019年第十届蓝桥杯国赛B组试题B-质数拆分-01背包问题+素数筛选的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。