个人建立网站,360提交网站入口,沈阳网站制作思路,快速搭建一个网站问题描述】
2019可以被分解成若干个两两不同的素数#xff0c;请问不同的分解方案有多少种#xff1f;
注意#xff1a;分解方案不考虑顺序#xff0c;如 2 2017 2019 和 2017 2 2019 属于同一种方案。答案#xff1a;55965365465060
代码如下#xff1a;
#includ…问题描述】
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;i2019;i){if (!vis[i])for (int j i*i;j2019;ji) vis[j] true;}for (int i 2;i2019;i) {if (!vis[i]) p[k] i;}
}int main()
{is_prime();dp[0][0] 1;for (int i 1;ik;i)for (int j 0;j2019;j){dp[i][j] dp[i-1][j];if (j p[i]) dp[i][j]dp[i-1][j-p[i]];}coutdp[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;i2019;i){if (!vis[i])for (int j i*i;j2019;ji) vis[j] true;}for (int i 2;i2019;i){if (!vis[i]) p[k] i;}
}int main()
{is_prime();dp[0] 1;for (int i 1;ik;i)for (int j 2019;jp[i];j--){dp[j] dp[j-p[i]];}coutdp[2019]endl;return 0;
}
