蓝桥杯2300 质数拆分

问题描述

将 2022 拆分成不同的质数的和，请问最多拆分成几个？

01背包问题

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

int prime[2025];
int dp[2025]; //dp[j]：和为 j 时的最多拆分质数个数

//2022数较小，使用普通的质数判断函数
bool is_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;
}

int main()
{
int cnt=0;
for(int i=2; i<=2022; ++i)
{
if(is_prime(i))
{
cnt++;
prime[cnt] = i;
}
}

for(int i=1; i<=cnt; ++i)
{
//倒序，避免重复使用同一个质数
for(int j=2022; j>=prime[i]; j–)
{
dp[j] = max(dp[j], dp[j-prime[i]] + 1);
}
}

cout<<dp[2022];

return 0;
}