A40233. 质数拆分
填空题
困难
知识点
题目描述
质数拆分
题目描述
2019可以被分解成若干个两两不同的素数，请问不同的分解方案有多少种？
注意：分解方案不考虑顺序，如 2 + 2017 = 2019 和 2017 + 2 = 2019 属于同一种方案。
参考答案
#include <iostream>
using namespace std;
const int N = 2500;
int k = 1;
int st[N], prime[N];
long long f[N];
void init()
{
for (int i = 2; i <= 2019; i ++)
{
if(!st[i])
{
prime[k ++] = i;
for (int j = i + i; j <= 2019; j += i) st[j] = true;
}
}
}
int main()
{
init();
f[0] = 1;
for (int i = 1; i < k; i ++)
for (int j = 2019; j >= prime[i]; j --)
{
f[j] += f[j - prime[i]];
}
cout << f[2019] << endl;
return 0;
}答案解析
答案：55965365465060
上一题
下一题