题目描述

将 20192019 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？

注意交换顺序视为同一种方法，例如 2 + 2017 = 20192+2017=2019 与 2017 + 2 = 20192017+2=2019 视为同一种方法。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
vector<int>ans;
int cheak(int a){
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return 0;
    }
    return 1;
}
void add(int n){
    for(int i=2;i<=n;i++){
        if(cheak(i)){
            ans.push_back(i);
        }
    }
}

int main(){
    int n=2019;
    add(n);
    long long dp[2020]={0};
    dp[0]=1;
    for(int i=0;i<ans.size();i++){
        //dp[i]=1;    
        for(int j=2019;j>=ans[i];j--){
            dp[j]+=dp[j-ans[i]];
        }
    }
    cout<<dp[2019];

    return 0;
}